Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice.
Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal <[email protected]> wrote: > consider an array having n elements.....out of which one number is > repeated twice....other number are repeated odd number of times(for > simplicity, assume other numbers are occurring just once).... > > can you find the number that is repeated twice in O(n) time??? > > PS: numbers are not from a particular range..... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Somnath Singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
