puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Randy Howard on 10 Jul 2005 19:20 CBFalconer wrote (in article <42D139A2.EEF0DF8B(a)yahoo.com>): > spinoza1111(a)yahoo.com wrote: >> > ... snip ... >> >> Does he, Karen? And who is this "boss"? >> >> Is he Ken Lay of Enron? Odds are that Ken Lay didn't want his > ... snip ... > > He's baaaack. Expanding a 50 line posting to 160 lines of > non-responsive off-topic bilgewater. Perhaps he is out of work again. It seems to get much worse during those periods. -- Randy Howard (2reply remove FOOBAR)
From: Joe Seigh on 10 Jul 2005 21:51 Willem wrote: > )> Method 1: Determine the xor of the numbers 0...n, then xor the > )> sequence. Xor the two results to get the missing number. > > Joe wrote: > > ) That's the O(2n) solution. > > Are you sure it takes O(n) time to find the xor of the numbers 0..n ? Well, in this case n = n + 1. :) > > Anyway, this and the solution below are variations on the same theme. > > )> Method 2: Determine the sum of the numbers 0...n, then the sum of the > )> sequence. The difference of the two sums is the missing number. To > )> avoid overflow/underflow do the sums module n+1. > > Ok, I was looking for different variations then. Anyway the answer I was looking for was for n being an odd number, xor all the numbers together if (n+1)/2 is odd and result is even, xor result w/ 1 if (n+1)/2 is even and result is odd, xor result w/ 1 The full sequence can be written as (0+0), (0+1), (2+0), (2+1), .... ((n-1)+0), ((n-1)+1) the numbers module 2 being repeated with even or odd lsb. xor'ing the numbers together gives you the missing number except for the lsb which you correct depending on the sequence length, i.e. whether the number of odd numbers is even or odd. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: pete on 10 Jul 2005 22:15 Joe Seigh wrote: > That's the O(2n) solution. There's no such thing as O(2n). It's just O(n). -- pete
From: Richard Harter on 11 Jul 2005 00:15 On Sun, 10 Jul 2005 21:35:01 GMT, cri(a)tiac.net (Richard Harter) wrote: >Method 2: Determine the sum of the numbers 0...n, then the sum of the >sequence. The difference of the two sums is the missing number. To >avoid overflow/underflow do the sums module n+1. A prettier way to do this is to compute sum(i -a[i]) for i=1...n Alternatively subtract sum(a[i]) from n*(n+1)/2. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: Chris Sonnack on 11 Jul 2005 13:57
CBFalconer writes: > a b XOR(a,b) > = = ======== > F F F > F T T > T F T > T T F > > Some have been known to learn this without attending grad school. Some learned it in high school. -- |_ CJSonnack <Chris(a)Sonnack.com> _____________| How's my programming? | |_ http://www.Sonnack.com/ ___________________| Call: 1-800-DEV-NULL | |_____________________________________________|_______________________| |