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
Pubblicato da a
Reazioni: 

2 comments:

  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)

    code:
    https://gist.github.com/878167

    ReplyDelete

  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.

    ReplyDelete

Subscribe to: Post Comments (Atom)