Given an integer array of repeating numbers. All but one number repeats an odd number of times. Find that number in O(n) time and no additional data structure?

Here is an example about the question. If we have an array = {3, 2, 1, 2, 1}, number 2 and 1 repeat two times (even number of times) while number 3 repeats only once (odd number of times). Thus, the answer to our question will be number 3.

This question is relatively easy if we are allowed to use an additional data structure. For example, we can use a hash table to maintain counts of repetition for each number in the array. Then, we look for the number with odd count. However, since we can't use additional storage, the question becomes difficult.

Well to answer this question, we need to use bit manipulation. Take a look at the code below:

int findOddRepeatInArray(int arrayToFind[], int arraySize)
{
  int result = 0;
  for (int i = 0; i < arraySize; i++)
  {
    result ^= arrayToFind[i];
  }
  return result;
}

Wow, that's much shorter and efficient than using hash table! However, this requires the knowledge of bit manipulation which is a scary topic :( for a lot of programmers.

The caret '^' sign means XOR (exclusive OR). And, our algorithm works because XOR of two same number is 0. For example, 2 XOR 2 = 0 because 0010 XOR 0010 = 0000. Thus, all the even repeating numbers will yield the result = 0 while the odd repeating number will yield itself as the result. In our example, we know 3 is the odd-repeating number because 3 XOR 0 = 3.