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

Richard Harter wrote:
> 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.

That's the O(2n) solution.
> 
> 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.

That's the standard solution.
> 
> 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.

O(2n) but probably not O(1) size in the sense we're looking for.
Good solution of that type. Avoids a sort.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.