Subj : Re: puzzle
To   : comp.programming
From : Joe Seigh
Date : Sun Jul 10 2005 10:51 pm

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.

.