Odd Occurrences In Array Algo and Implementation in Python
A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
the element at index 5 has value 7 and is unpaired.
XOR Operation : It is a bit wise logical operation that only returns true if both the inputs are the same
Properties of XOR
Here are several useful properties of XOR. This applies to plain XOR and bitwise XOR.
x (+) 0 = x XORing with 0 gives you back the same number. Thus, 0 is the identity for XOR.
x (+) 1 = \x XORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different:
x ^ ~0 = ~x . That is, if you XOR with all 1's, the result will be the bitwise negation of x.
x (+) x = 0 XORing x with itself gives you 0. That's because x is either 0 or 1, and 0 (+) 0 = 0 and 1 (+) 1 = 0.
XOR is associative.That is: (x (+) y) (+) z = x (+) (y (+) z).
You can verify this by using truth tables.
XOR is commutative.That is: x (+) y = y (+) x.
Implementation1: Using Bit wise XOR(^)
result =0for number in A:
result = result ^ number