Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 4 down vote favorite

I was asked this in an interview, and I'm not sure what the answer is.

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.

share|improve this question
so they give u a list or array and then u have to find pair ? – Babban Shikaari Mar 18 '11 at 0:55
do u have to find just one pair or all the pair from the given data structure? – Babban Shikaari Mar 18 '11 at 0:56
How about 1 and -1? Or 0 and 0? – GregS Mar 18 '11 at 0:57
belongs on programmers.stackexchange.com. – Daniel A. White Mar 18 '11 at 0:58
Were they asking you to write a program or describe an algorithm to do this? – Lord Torgamus Mar 18 '11 at 2:20

migrated from stackoverflow.com Mar 18 '11 at 1:00

5 Answers

up vote 3 down vote

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
share|improve this answer
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 4:39
up vote 3 down vote

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

share|improve this answer
1  
+1 perfect in every way... for programming or algo. – Shine Mar 18 '11 at 5:16
You got the job! – systemovich 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. – davidk01 Mar 18 '11 at 17:58
up vote 2 down vote

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

share|improve this answer
up vote 1 down vote

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).
share|improve this answer
up vote 1 down vote

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.