Finding a missing number in an array using XOR logic

Sunday, July 1, 2012

This python program illustrates the way to find a missing number in an array (list) using XOR logic.


"""
   Code to find the missing number using XOR gate
   Author: S.Prasanna
"""

def XOR(input_list):
    """ XOR all elements in a list """

    def recXOR(index):
        if index == 0:
            return input_list[0]
        else:
            return input_list[index] ^ recXOR(index - 1)

    return recXOR(len(input_list)- 1)

if __name__ == "__main__":
    input_list = [ -4, -2, 5, 6, 80 ]
    print "Input list =", input_list
    XOR1 = XOR(input_list)
    print "XOR of all elements in the list (XOR1) =", XOR1

    for index, value in enumerate(input_list):
        element = input_list.pop(index)
        print "Removed element %d from the list" % element
        XOR2 = XOR(input_list)
        print "New XOR of all items (XOR2) =", XOR2
        print "Missing element (XOR1 ^ XOR2) =", XOR1 ^ XOR2
        input_list.insert(index, element)
Syntax highlighter: Pygments

Sample Output:

>>>
Input list = [-4, -2, 5, 6, 80]
XOR of all elements in the list (XOR1) = 81
Removed element -4 from the list
New XOR of all items (XOR2) = -83
Missing element (XOR1 ^ XOR2) = -4
Removed element -2 from the list
New XOR of all items (XOR2) = -81
Missing element (XOR1 ^ XOR2) = -2
Removed element 5 from the list
New XOR of all items (XOR2) = 84
Missing element (XOR1 ^ XOR2) = 5
Removed element 6 from the list
New XOR of all items (XOR2) = 87
Missing element (XOR1 ^ XOR2) = 6
Removed element 80 from the list
New XOR of all items (XOR2) = 1
Missing element (XOR1 ^ XOR2) = 80
>>>

1 comment:

Paulo José said...

Maybe I'm missing something, but it should work with sum too.

Input list = [-4, -2, 5, 6, 80]
SUM1 = 85

Remove element -4
SUM2 = 89

Number removed = SUM1 - SUM2 = -4

So, what the point of using XOR?


Copyright © 2016 Prasanna Seshadri, www.prasannatech.net, All Rights Reserved.
No part of the content or this site may be reproduced without prior written permission of the author.