ansaurus

Question

Need help with a math trick question

Answer 1

+4 A:

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 2010-09-16 06:56:56

doesn't seem to work... N refers to the number of numebrs and not a value on its own.

Ali 2010-09-16 07:01:46

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 2010-09-16 07:05:18

@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 2010-09-16 07:07:29

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 2010-09-16 07:17:05

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 2010-09-16 07:22:18

@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 2010-09-16 07:33:30

ah - I got it - was reading the question wrong it seems..

Ali 2010-09-16 07:48:54

Answer 2

+1 A:

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.

kohomologie 2010-09-16 06:59:12

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 2010-09-16 07:09:43

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.

kohomologie 2010-09-16 07:11: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.

kohomologie 2010-09-16 07:12:02

OK Im lost here - basically I have the SUM and the number of numbers - but need to know what numnber was duplicated

Ali 2010-09-16 07:15:51

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.

kohomologie 2010-09-16 07:19:45

Answer 3

+1 A:

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.

Gamecat 2010-09-16 07:14:32

ansaurus

tags:

views:

answers:

Need help with a math trick question

related questions