XOR is the best computationally as well as space complexity.
On 1/16/07, Satish <[EMAIL PROTECTED]> wrote:
Hangjin Zhang wrote: > Do an XOR on all numbers. The resulte is the number which occurs only once > > HZ > > On 12/30/06, Abhishek <[EMAIL PROTECTED]> wrote: > > > > > > Hi, > > Suppose I have a sequence of numbers in which every number occurs twice > > in the sequence except one. Whats the fastest way of finding that > > number which occurs only once? > > With Regards, > > Abhishek S > > > > > > > > > I am not sure how XOR will be defined on numbers. Also, calculating XOR for any sequence of N numbers where N is not known a priori is computationally very expensive. A simple way could be to keep additional large bit vector memory. where we have 2 bits per number. For each number visited in sequence, mark the corresponding bit b1 as visited once. On revisiting, mark another corresponding bit b2. At the end, just look for the number that has only b1 set and b2 unset. SKM >
--~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
