Array: Find the number with odd number of occurrences

Problem: You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.

Solution: A naive approach would be to loop over the elements of the given array and keep a count of each integer in a hash table or another counter array. But, this quickly becomes unfeasible as the range of integers could be 2^31 (one less). This is an O(n) solution that takes at memory O(range(n)).

The next approach is to sort the array and then loop on it counting occurrences of the integers. When there is a change in the integer we check its count to see if its odd or even. If its odd we have found our special integer. This is an O(n log n) solution that uses constant memory.

Lets try to see if we can use the property that there is one number that occurs odd number of times and every other number occurs even number of times. Since an even number is divisible by 2, you could think of the even occurrences as being present in pairs. The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR will do the trick. Its gives you O(n) solution with no extra memory.

Ex: 3,5,3,2,2
 011  -- 3
^101  -- 5
----------
 110
^011  -- 3
----------
 101
^010  -- 2
----------
 111
^010  -- 2
----------
 101  -- 5 (special one)
Code:
//
// will return the number with odd number of occurrences
// will return 0 if all numbers occur even number of times
//
int GetSpecialOne(int[] array, int length)
{
   int specialOne = array[0];
   
   for(int i=1; i < length; i++)
   {
      specialOne ^= array[i];
   }
   return specialOne;
}

8 comments:

  1. The XOR one is a super brilliant answer. Thanks for posting it and making us think in that direction.

    ReplyDelete
  2. Very beautiful answer, just got that trick today in interview, wish I had thought about it!

    ReplyDelete
  3. Then the question becomes how do you deal with exceptions, such as your given an array for this method but it has 2 or more numbers that appear an odd amount of times... is it possible to create another array containing the entire exclusion set from XOR? I thought i would through that out there. Going to check on it myself...

    ReplyDelete
    Replies
    1. When I was trying to solve this myself (without thinking of the XOR method), I came up with a way that should work for that as well as non-numerical elements, while retaining the O(n) time and space complexity.

      Create an initially empty hash table. Go through the list of objects (number, in this case) one at a time, and add each item to that hash table; as long as when adding to a hash table you don't encounter a collision. If you do encounter a collision, remove the item from the hash table and the initial list. In the end, you will have a list of only odd occurring objects.

      There may be a faster/better way, but this is what came to mind for me first.

      Delete
  4. what if the problem is to find odd in array with all even occurrences except one ?

    ReplyDelete
  5. awesome method... thanx for posting

    ReplyDelete
  6. I was asked this question in my second round of amazon phone interview. I got the first two solutions, but did not get the third solution. Also would someone care to explain why the second method is O(nlogn) and not just O(n)?

    ReplyDelete
  7. I'm going to answer my own question on why the second approach is O(nlogn) -- it depends on the sorting method used!

    ReplyDelete