Good catch, Vikram. I had a wrong assumption that the pair (i, sumofXY-i) would uniquely match with xorofXY. Here is a counter example to disprove my solution. Suppose X is 5 (binary 101) and Y is 6 (b 110), whose XOR would be 3 (b 011). But, moving unit bit from 5 to 6, we have a pair 4 (100) and 7 (111), which also has the same sum and same XOR. Hence the disproof!
I wanted to avoid multiplication and leverage XOR, but overlooked a subtle property. Is there really a way to leverage XOR for this problem? Note: The SOLUTION I posted before for this problem is WRONG. My apologies! Thanks, Channa On Thu, Jul 30, 2009 at 12:51 PM, Vikram Venkatesan < [email protected]> wrote: > *for i=1 to sumofXY/2* > *if (xorofXY XOR i XOR (sumofXY-i)) is zero* > *then x is i, y is (sumofXY-i)* > *endfor* > > Channa, is this logic based on the assumption/fact that no other other pair > of numbers (m, n) can have the same XOR and SUMMATION as that of the (x, y) > pair? If so, could you please explain it? > > > On Thu, Jul 30, 2009 at 12:04 AM, Prabhanjan ananth > <[email protected]>wrote: > >> Let the 2 missing numbers be a and b . >> Let the sum of the 2 missing numbers be S , product be P . >> >> a+b=S -(1) >> ab=P -(2) >> >> Solve (1) and (2) >> >> >> On Wed, Jul 29, 2009 at 7:30 PM, Vikram Sridar <[email protected] >> > wrote: >> >>> nice one channa.. much like my solution.. same complexity n memory >>> requiements >>> but pulling that wonderful use of the Xor gate was great show indeed.. >>> very impressive solution >>> >>> >>> >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
