2

Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)

Hi guys, I wasn't sure where to ask this but since this is an algorithmic question here it goes. I've come face to face with a math problem and can't seem to get over it for the last couple of days. It goes like this:

You are given an adding machine that sums a set of N+1 digits consisting of positive integers 1 to N as it's given the numbers (e.g. the machine is given 3 as the first number and outputs 3. It's then given 6 as the second number and outputs 9. It's given 11 as the third number and outputs 20. Etcetera until it has processed N+1 numbers). One (and only one) of the digits is repeated. How do you determine which number is repeated?

It seems like a trick question and I'd be really annoyed if it is just that a question to which the answer is 'not possible' - any ideas here?

Community
  • 1
  • 1
Ali
  • 7,353
  • 20
  • 103
  • 161

3 Answers3

4

Subtract (1+2+..+N) = N*(N+1)/2 from the sum.

EDIT: in case N is not known, find the largest triangular number smaller than the given sum and subtract.

Henrik
  • 23,186
  • 6
  • 42
  • 92
  • doesn't seem to work... N refers to the number of numebrs and not a value on its own. – Ali Sep 16 '10 at 07:01
  • no wait I don't get it lets assume teh numbers were added as 3, 6, 11, 6 - so now N is 4. How can I tell given that I enter 6 and only have the sum of the values? – Ali Sep 16 '10 at 07:05
  • 2
    @Ali: from your description: " a set of N+1 digits consisting of positive integers 1 to N". But 6 and 11 are outside 1..4. – Henrik Sep 16 '10 at 07:07
  • uh how so I mean I got this question on a job interview and have reproduced it in its entirety. I'm a bit perplexed as to what N+1 refers to it seems boyond my realm of mathematics or I'm forgetting my numerical methods classes here... – Ali Sep 16 '10 at 07:17
  • 1
    This is how I read the question: summed numbers: [1,2,3,3,4], N = 4; sum = 13, 13-4*5/2 = 13-10 = 3 – Henrik Sep 16 '10 at 07:22
  • @Ali: There are N numbers from 1 to N; N of the numbers it sums are unique; therefore by the pigeonhole principle it sums all the numbers from 1 to N. Plus an additional number which is repeated. Given N (and it seems we are), this question isn't really a trick. – Potatoswatter Sep 16 '10 at 07:33
  • ah - I got it - was reading the question wrong it seems.. – Ali Sep 16 '10 at 07:48
1

If you know N and the sum S, the answer is d = S - N*(N+1)/2. This is because the sum of all numbers from 1 to N is a triangular number, and each number from 1 to N occurs once (except for one that is repeated).

If you do not know N, you can take N = floor((sqrt(8*S+1)-1)/2. That can be deduced from a quadratic equation (n^2 + n)/2 = a.

Marat Salikhov
  • 6,367
  • 4
  • 32
  • 35
  • I tried this with the following numbers [3, 6, 10] = 19, adding 6 to this sum give me 25 so 4*(4+1) = 20, 20/2 = 10 but 25 - 10 gives me 15...I want to tell if a number is repeated and which one is? WHich branch of mathematics is this? – Ali Sep 16 '10 at 07:09
  • These do not conform to your problem description. These numbers do not belong to 1..3. More than that, 4 is not N, but N+1. As for branch, it is elementary combinatorics. – Marat Salikhov Sep 16 '10 at 07:11
  • And if you take arbitrary numbers in this problem, it becomes basically unsolvable unless you know the sum of all distinct numbers in advance. – Marat Salikhov Sep 16 '10 at 07:12
  • OK Im lost here - basically I have the SUM and the number of numbers - but need to know what numnber was duplicated – Ali Sep 16 '10 at 07:15
  • 1
    But your problem description states that all those numbers belong to `1..N`, where `N+1` is a number of numbers! That is, there are all numbers from 1 to N and one duplicate, also between 1 and N. See an example: N = 5, numbers are 1,2,3,4,5,3. The duplicate is 3. The sum of all numbers is 18. N is 5, we have N+1 = 6 numbers here. So d is = 18 - 5*6/2 = 3, as expected. – Marat Salikhov Sep 16 '10 at 07:19
1

Ok, you have:

X = 1 + 2 + ... + N + p,  where 1<=p<=N

Or

X = N(N+1)/2 + p, 1<=p<=N

Declare:

S(N) = N(N+1)/2

And you know that

S(N) < X < S(N+1), because 1<=p<=N

You can find N, by finding the S(N) such that S(N)X.

If you have found S(N), subtract it from X and you find the duplicate number.

Toon Krijthe
  • 52,876
  • 38
  • 145
  • 202