sets of numbers that sum to a certain number?

Question

I was asked this in an interview, and I'm not sure what the answer is or how to approach the problem.

Find a pair of numbers that sum up to zero (or any other number), then find three (and then four) numbers that sum up to zero.

so they give u a list or array and then u have to find pair ? — Babban Shikaari, Mar 18 '11 at 00:55
do u have to find just one pair or all the pair from the given data structure? — Babban Shikaari, Mar 18 '11 at 00:56
Were they asking you to write a program or describe an algorithm to do this? — Pops, Mar 18 '11 at 02:20

score 3 · Answer 1 · answered Mar 18 '11 at 04:50

3

Use the following equality 1+2+3+...+n=n(n+1)/2.

1+(-1) = 0

1+2+(-3) = 0

1+2+3+(-6) = 0

...

1+2+3+...+n+(-n(n+1)/2) = 0

answered Mar 18 '11 at 04:50

1

+1 perfect in every way... for programming or algo. – Shine Mar 18 '11 at 05:16
You got the job! – Geoffrey Mar 18 '11 at 13:16
@Geoffrey van Wyk: I don't think I would have gotten this on the interview. It's the kind of thing where you have to be in the right state of mind and interviews put me too much on edge to think creatively. – Mar 18 '11 at 17:58

score 2 · Answer 2 · answered Mar 18 '11 at 01:03

2

why don't you just pick a number and it's inverse element in + so for example 1 and -1 ?

if you need to find 4 6 8 and so on you can just use 1, -1, 2, -2, 3, -3 and so on.

for 3 numbers 3,-2,-1

answered Mar 18 '11 at 01:03

tokam

121
2

score 2 · Answer 3 · answered Mar 18 '11 at 01:11

This is what i could analyze in a minute or two to make a pattern:

Pair Sum as zero: For any pair to be zero, for any number find the negative of that number For example, (10, -10). One exception ofcourse is (0,0).
Three Number sum as zero: For 3 numbers, Sum of any two numbers should be equal to the negative of third number. For example, ((1,2), -3) or ((-1,-2),3). So, take sum of two numbers and find the negative of that sum. One possible exception is ofcourse (0,0,0)
Four number sum as zero: For 4 numbers, either sum of three numbers should be negative of 4th number or sum of two numbers would be the negative of other two numbers. For example, ((1,2,3),-6) or ((1,4), (-2,-3)). One possible exception would be (0,0,0,0).

score 2 · Answer 4 · answered Mar 18 '11 at 01:50

2

Incredibly stupid question ....... since it didn't specify UNIQUE numbers the answer is 0!

0 + 0 = 0
0 + 0 + 0 = 0
0 + 0 + 0 + 0 = 0

answered Mar 18 '11 at 01:50

ennuikiller

1,168
7
8

1

The question is unclear, but I'd wager that he had to find the pair of numbers, three numbers, four numbers, etc. within a pre-existing collection of numbers, not just make them up! – Carson63000 Mar 18 '11 at 04:39

score 0 · Answer 5 · answered Mar 18 '11 at 01:19

Since you didn't say they had to be integers (or different numbers)

Number - Number

Number - Number/2 - Number/2

Number - Number/3 - Number/3 - Number/3

Etc.

Easy pattern to toss in a loop - though @gpmattoo has a much more elegant solution. (The sum of the first X number minus that sum as the last number).

sets of numbers that sum to a certain number?

5 Answers5