[algogeeks] Re: Finding repeated element in most efficient way

[Shyam]

I think I could do it in O(n) .

var bits=0
var @array

for each i in array
    if (bits & i)!=0
          return i
    else
          bits=bits | i;
    end if
end for

I just use the pattern for powers of two

let array be 2,4,2

so first
bits=0 i=2     so bits(000) & i(010) is 0 so bits= bits | i which is
bits=010
next
bits=2 i=4     so bits(010) & i(100) is 0 so bits= bits | i which is
bits=110
next
bits=6 i=2     so bits(110) & i(010) is 2 which is !=0 so we return i.

I think that should be it.

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---