CareerCup

This can be done in expected O(1) time if you unleash the power of randomization.

Pick two distinct indices at random and get the values there. If they are the same, you've found the identical element. If not, repeat this process. Each time you try this, the chance of success is roughly 1/4 (the first element is one of the identical elements with 1/2 probability, and the second element is one of the identical elements with (n/2-1)/n probability, which is almost 1/2 for all but the smallest of inputs). Therefore, the expected number of attempts needed is ~4, which is O(1) attempts. Each attempt just requires looking at 2 random elements, which takes O(1), so this entire algorithm is O(1) in the expectation.

Without randomization, it's not possible to solve this in less than O(N) because an adversary that knows your algorithm would be able to predict all the locations you will read in advance and place only distinct elements in them, ensuring you never see the identical element until you've first read up to N/2-1 locations, which takes O(N) time.

Use hash map. In worst case, you will get answer after visiting first (N/2 + 2) numbers.

Are you posting questions off the web?

The point is that the other half is distinct !

So

2 2 1 7 8 9 2 2

So all we need to do is just start reading the list and see if at least one element is repeated.
1. Put each element to a hash and get the count of each element.
2. If even one element got repeated once, we got our odd one out.
3. Worst case run time for this is n/2 (But still O(n) :( )
4. Once we got the odd one out, every other element is distinct.

Do we need something like "boolean isElementUnique(int x)"?

If you want to find identical that can be done in O(n)