
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 n1 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..(n1) 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,.......,n1
Summation of this series is Sn= (n1)*n/2
Now the series which we have 1,2,3,....x,x,....n1
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 1n)
i = sequence[n];
while(sequence[i])
{
i = sequence[i];
sequence[i] = 0;
}
ANSWER = i;
Aaron
Wednesday, May 21, 2003
Recent Topics
Fog Creek Home
