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

Willem 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 ?
> 
Well, the standard solution for one.  This is a standard whiteboard question.
This is also a slightly reformulated version of the problem being discussed
already.  A slight hint.  n should be an odd number but it doesn't really
matter.  You can solve it if n is even.   You can also go for a O(2n) solution
if that makes it any easier.


-- 
Joe Seigh

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

.