Subj : Re: puzzle
To   : comp.programming
From : cri
Date : Sun Jul 10 2005 10:35 pm

On Sun, 10 Jul 2005 20:52:12 +0000 (UTC), Willem <willem@stack.nl>
wrote:

>Joe wrote:
>) Willem wrote:
>)> Joe wrote:
>)> ) To make things interesting, this problem should be reposed as,
>)> ) you have a unordered sequence of the numbers 0 to n with one
>)> ) number missing and the others appearing only once.  Find two
>)> ) O(n) ways of determining the missing number.
>)> 
>)> O(n) time and how much memory ?  O(1) ?  O(n) ?
>)> 
>) O(1)
>
>Well, I can only think of one solution offhand, with a few variations.
>I'm assuming you mean fundamentally different solutions ?

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.

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.

For extra credit, give a method not a simple variation.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

.