See the original problem on HackerRank.
Alan has finally reached the final round of interviews at Gugol. He is one step from catching the job he loves and he has to impress the interviewer with a killer answer to the last question.
The problem looks like very easy: given an array where all elements appear even number of times except one. All repeating occurrences of elements appear in pairs and these pairs are not adjacent (there cannot be more than two consecutive occurrences of any element). Find the element that appears odd number of times.
For example:
\({2, 2, 1, 2, 2, 1, 1}\) is a valid input, but \({1, 2, 2, 2, 2}\), \({2, 2, 2, 1}\) and \({2, 1, 2}\) are not.
Alan cannot give a naive answer to the question, though. He needs to design a solution that is better than linear and does not use extra memory!
Can you help Alan?
Input Format
The first line contains \(T\), the number of test cases.
For each test case you read:
 an integer \(N\)
 \(N\) numbers separated by whitespaces
Constraints
 \(1 \leq T \leq 10^3\)
 \(1 \leq N \leq 10^6\)
 Array numbers are 32bit integers
Output Format
Print the odd appearing element on a new line for each testcase.
Solutions
We call this kind of challenges “constrained”, meaning that we limit the admittable solutions space by applying some special constraints.
Generally, this means that the solution could be find more easily if we do not have such constraints.
In this case, we have a constraint on both time and space complexity (we want a lineartime and constantspace solution). In other examples we can “disable” some operations or using a certain input format, etc.
Some naive solutions
Scanning the array
Finding the odd occurrence by scanning the array (e.g. find the first element different from the previous and next ones)


The previous approach could be generalized in case the domain changes by sorting the array (e.g. the input format changes)
XOR
Better than the previous and enough generic is using xor (see here)


A more functional approach using fold (called std::accumulate
in C++)


Haskell:


Better than linear
A betterthanlinear solution requires \(O(LogN)\) time. It applies a variation of binary search.
All elements before the odd occurrence have the first occurrence at even index [0, 2, ..]
. After the odd element they follow the opposite pattern, with the first occurrence at odd index [1, 3, ..]
.
When we divide the space in two halves we check if the middle index is even or odd:
 if even, we check if the underlying element is the same as the next one:
 if so, the pattern is maintained and we search the right side
 otherwise, the pattern has been broken somewhere before so we search the left side
 if odd, we basically do the opposite of the idea above. This time we check the element before it:
 if the same, the pattern is maintained and we search the right side
 otherwise, the pattern has been broken somewhere before so we search the left side.
Here is an implementation (courtesy of GeeksForGeeks):


Here is an alternative iterative version in Python by Serena Ziviani:


Alternative version in C++ by Alessandro Pezzato without recursion, with some esoteric optimization using bitwise operators.


This challenge shows that, after all, the binary search pattern can be applied as far as we have a deterministic update rule which moves to only one half of the divided search space.