Fog Creek Software
Discussion Board




sum it up

Strictly speaking, the answer is wrong.  It takes O(log(n)) bits to store the sum of the numbers.  Actually, the problem is impossible to solve as written, because you can't even allocate a single temporary variable to store n-1 without using O(log(n)) bits.

Of course, in practice, usually the size of a machine's address space is determined by its machine word size, so if you had a list of 1..(n-1) numbers in memory, you'd be on a machine with a register of log(n) size.  OTOH, if you stored the list of numbers on disk, or received them over a socket from a program or the network, then you could potentially receive a list of numbers where n exceeds MAX_INT.

~k
Tuesday, April 15, 2003

Let the series be from 1,2,3,.......,n-1

Summation of this series is Sn= (n-1)*n/2

Now the series which we have 1,2,3,....x,x,....n-1


Let us find the sum for the above said series and
Let this value be SUM

Since x is said to be repeated

i.    SUM > Sn and
ii.  SUM minus Sn is the repeated number.


If i am wrong let me know.

Karthik Muthu
Monday, April 21, 2003

Oops ,
Sorry for the repost,

I didn't look at the solution properly

Thanks

Karthik Muthu
Monday, April 21, 2003

Actually, this whole answer is making it too complex!

Just generate the next expected number
(simple counting)
and flag a mismatch!

Now we can handle any number of repeats
and use only the memory for the counter.

James Schettine
Wednesday, April 23, 2003

I have seen this problem before.  The obvious answer, as pointed out (but not described clearly)...is to sort the array and then walk it to find the dupe. 

From there, an interesting constraint is to make the algorithm O(n).

Solution:
(assume array indexed 1-n)
i = sequence[n];
while(sequence[i])
{
    i = sequence[i];
    sequence[i] = 0;
}

ANSWER = i;

Aaron
Wednesday, May 21, 2003

*  Recent Topics

*  Fog Creek Home