Thursday, March 17, 2011

Find single element

You are given an array A that contains integers. Every integer occurs 3 times in A leaving one integer that appears only once. Fastest way to find that single integer


  1. Need to look through entire array (of a length N) to be sure, and one approach could be to use 2 hash tables while doing that, one for occurence (or count) of all element numbers and one for occurence of single elements - this can be done in O(N)


  2. The vector contains n+1 unique and 2*n reps, so I can stop when the size of first hash reaches n+1 items.