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   Fog Creek Home