Subj : Re: puzzle
To   : comp.programming
From : Willem
Date : Mon Jul 11 2005 12:02 am

)> 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 ?

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.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.