The problem could be solved using xor logic. First take xor of all the
elements .Doing that we get a value which is xor of the two non repeating
elements(as xor of similar values is 0). Now xor of two non repeating
numbers contains bits set at those places where the two numbers differ. Now
if we take any set bit of our result and again xor all those values of set
where that bit is set we get first non-repeating value. Taking xor of all
those values where that bit is not set gives the another non-repeating
number..
For ex
let a[]={2,3,4,3,2,6}xor of all values=0010 Now we need to get any set bit. We can extract the rightmost set bit of any number n by taking ( n & ~(n-1)) Here 2nd bit is the rightmost set bit. Now when we take xor of all values where 2nd bit is set(this could be done as (a[i] & 0010) , we get 6 Taking xor of all values where 2nd bit is not set yields 4. Mukesh Gupta Delhi College of Engineering On Mon, Oct 4, 2010 at 3:17 PM, malli <mallesh...@gmail.com> wrote: > I have an array. All numbers in the array repeat twice except two > numbers which repeat only once. All the numbers are placed randomly. > Goal is to find out efficiently the two numbers that have not > repeated with O(1) extra memory. Expecting linear solution. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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?hl=en.
