Subj : Re: puzzle
To   : comp.programming
From : Willem
Date : Sun Jul 10 2005 10:41 pm

Richard wrote:
) Method 1:  Determine the xor of the numbers 0...n, then xor the
) sequence.  Xor the two results to get the missing number.
)
) 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.

I would call those variations on a theme, to be honest.

) Method 3: If you can reorder the sequence, partition it into two
) halves (the criteria can be size, or odd/even), determine which
) partition is missing an element, and repeat as needed.

Ah, should have thought of that one, especially given the whole
discussion with the conclusion that it is, in fact, an O(n) solution.


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

.