Search code examples
c++carraysbit-manipulationxor

Can we find if 0 occurs odd number of times in an array using bit manipulation

I know that, XORing all elements of an integer array which contains all of its elements except 1 element occuring even number of times gives the number that occurs odd number of times.

Example

{ 1, 1, 2, 2, 3 }
1 ^ 1 ^ 2 ^ 2 ^ 3 = 3;

^ is XOR

What if the number occuring odd number of times is 0?
{ 1, 1, 2, 2, 0 } 

1 ^ 1 ^ 2 ^ 2 ^ 0 = 0    // Both give
1 ^ 1 ^ 2 ^ 2 = 0        // same answer

How to confirm that 0 is occuring odd number of times
PS : Prefer the answer code to be in C/C++

Solution

  • Let's call N, the number of elements in your array:

    • If (N is even) AND (XORing all elements ==0) -> All the elements occur even number of times
    • if (N is odd) AND (XORing all elements ==0) -> You single element is zero.

    This is how to check if an integer is even or odd in C / C++