This is a
solution to
problem 31 on the
hard interview questions node. If you have not read the
question, the
following will make no
sense to you:
Starting at the beginning of the array, test consecutive pairs for equality. If, for example, a(j) == a(j+1), continue by testing a(j+1) == a(j+2), etc. As soon as a(j) != a(j+1), remove those two elements from the array (suppose it’s a linked list) and continue by testing a(j-1) == a(j) (which used to be a(j+2)). Note that removing the two elements maintains the invariant that more than half of the elements have the same value. Once j is greater than half of the length of the remaining list, the element aj is the element we’re looking for, since a(0) == a(1) == ... == a(j). This runs in O(n) since no element appears on the right hand side of an equality test more than once.
This problem is similar to problem 30 on the hard interview questions node, and so is the solution.