Finding EVEN number of times repeating integer in an array where rest of the integers repeat ODD number of times

Question

Given is an array of integers. Each number in the array occurs an ODD number of times, but only 1 number is occurring an EVEN number of times. Find that number.

Below is the solution I read on stackoverflow that does NOT work. I am unable to find the link to that solution and I was wondering if somebody could help me understand why this solution is incorrect unless I am doing something wrong below.

We first XOR all the elements in the array. Lets call it aWithOutDuplicate which contains all the odd elements except for duplicate one. We then OR all the elements. Lets call it aAllUniquethat should contain all the unique elements. XORing aWithOutDuplicate and aAllUniqueshould spit out the duplicate element.

    int arr[] = {1,2,3,4,5,6,7,8,4,9};
    int aWithOutDuplicate = 0;
    int aAllUnique = 0;

    for(int i=0;i<arr.length;i++) {
      aWithOutDuplicate ^= arr[i];
      aAllUnique |= arr[i];
    }

   cout << (aWithOutDuplicate ^ aAllUnique);

Update: I wonder if this problem can be solved in O(n) time and O(1) space complexity.

Answer 1

This O(n), O(1) space solution works ONLY if the array elements are in the range [1,n-1] for an array of size 'n'. [Will work for [0,n-1] with a few tweaks mentioned below]

• Scan the array and do the following

  for(i=0; i < n; i++) 
    A[A[i]]=A[A[i]]*(-1)
  

• All array elements with odd occurrences will have a negative value at the end of the scan. The element with the even number of occurrence will have a positive value.

A few tweaks: If the array range is from [0,n-1], you can have a special case for '0' where you replace '0' with a special character during the first pass (instead of negation). You will have to revert back the special character back to '0' during the 2nd pass and so on.