Fog Creek Software
Discussion Board




Sum it on

http://www.techinterview.org/Solutions/fog0000000101.html

You may use the following:

if x1, x2, x3, x4 ... xN are your numbers, where x1=1,
and x2=2, etc.. and one number repeats once, you may
do this:

Sum(x1,...,xN) - xN(xN+1)/2  -> will give you the duplicate.

Adel
Thursday, October 16, 2003

what if you just get:

(x1 + x2 + ... + xN) - (x1 + x2 + ... + x(N-1) )

sag3
Wednesday, October 22, 2003

Basically, if you are given 5 numbers (lets say 1 2 2 3 4 )
Then, Sn=sum of first 5 natural numbers = n* (n+1)/2 = 15
Now, add the given numbers to get Sx=1+2+2+3+4=12
d=Sn-Sx=3
and n-d=repeated number=5-3=2
Thus in nutshell,
Repeated number= N - (Sn-Sx)
where,
Sn=Sum of first N natural numbers starting from 1
Sx=Sum of the given series containing a repeated number

aha!
:)

Gaurav Sachdeva
Monday, December 15, 2003

*  Recent Topics

*  Fog Creek Home