13
\$\begingroup\$

This is a Google interview question, see here for a youtube link.

The task:

Find 2 integers from an unordered list that sum to a given integer.

  1. Given an unordered list of integers, find 2 integers that sum to a given value, print these 2 integers, and indicate success (exit 0). They don't need to be any particular numbers (i.e. the first 2 integers summing to the right number), any pair that sums to the value will work.
  2. an integer is positive and greater than zero.
  3. a list of integers can be in any data structure including a file of integers - one integer per line.
  4. if no integers can be found, indicate a failure (exit 1).
  5. two integers at different positions in list must be returned. (i.e. you can't return the same number from the same position twice)

(Note: in the video, these are not exactly the requirements. The 'interviewer' changed his multiple times.)

eg.

sum2 8 <<EOF 1 7 4 6 5 3 8 2 EOF

Prints 3 and 5 and exit status is 0. Note that in this 1,7 and 2,6 would also be allowed results.

sum2 8 <<EOF 1 2 3 4

Returns exit status 1 since no possible combo. 4,4 isn't allowed, per rule 5.

Improve this question
\$\endgroup\$
16
  • 15
    \$\begingroup\$ This could have been a great question if it had had a chance to shake out some of the loose ends in the Sandbox first. For instance, for something like this I would expect to write a function that returned either a falsy value or a pair of numbers. \$\endgroup\$ Commented Mar 20, 2017 at 11:55
  • 2
    \$\begingroup\$ In the example, why is the returned pair is (3,5) and not (1,7)? \$\endgroup\$ Commented Mar 20, 2017 at 12:09
  • 4
    \$\begingroup\$ How can there be a "first" pair in an unordered list? That's inherently self-contradictory. \$\endgroup\$ Commented Mar 20, 2017 at 12:39
  • 23
    \$\begingroup\$ I don't really think the exit 0/exit 1 thing is a good idea. Many languages can't exist easily like that, and it's generally allowed to exit with an error (i.e. ignore STDERR) Many golfing languages don't even have an easy way to exit by exit code I think \$\endgroup\$ Commented Mar 20, 2017 at 14:22
  • 2
    \$\begingroup\$ On second thought, some answers have gone through some effort to produce exit code 1, so it may be better not to change the requirements now \$\endgroup\$ Commented Mar 20, 2017 at 18:06

26 Answers 26

Reset to default
5
\$\begingroup\$

Bash, 84 bytes

My implementation of (roughly) Google's engineer's solution but using bash and an input stream - not my solution, so this does not count.

while read V;do((V<$1))&&{ ((T=R[V]))&&echo $T $V&&exit;((R[$1-V]=V));};done;exit 1

Method

while we can read integer V from input stream if less than target $1 then if already seen $1-V then print $1-V and V and exit 0 (else) save candidate for input $1-V exit 1

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 9 bytes

h⊇Ċ.+~t?∧

Try it online!

Assuming I understood the challenge correctly…

Explanation

h⊇Ċ Ċ ('couple') has two elements, and is a subset of the head of the input Ċ. Output = Ċ .+~t? The sum of the elements of the Output is the tail of the Input ∧ (disable implicit unification)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Perl 6, 59 bytes

$_=get;put lines().combinations(2).first(*.sum==$_)//exit 1

Try it
Try it with no possible result

Expanded:

$_ = get; # get one line (the value to sum to) put # print with trailing newline lines() # get the rest of the lines of input .combinations(2) # get the possible combinations .first( # find the first one *.sum == $_ # that sums to the input ) // # if there is no value (｢Nil｣) exit 1 # exit with a non-zero value (｢put｣ is not executed)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript ES6, 58 70 68 64 bytes

a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]}

Returns a pair of numbers in the form of an array if found, otherwise returns undefined, a falsy value.

f=a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]} console.log(f([1,7,4,6,5,3,8,2])(8)); console.log(f([1,2,3,4,5,6,7,8])(8)); console.log(f([1,2,3,4])(8)); console.log(f([2,2])(4));

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ The example was 3, 5 but this outputs 1, 7... \$\endgroup\$ Commented Mar 20, 2017 at 12:06
  • \$\begingroup\$ @Neil, sorry, i have amended rules because I messed up. 1,7 is ok. \$\endgroup\$ Commented Mar 20, 2017 at 12:57
  • 1
    \$\begingroup\$ It won't work for f([2,2] 4) ? \$\endgroup\$ Commented Mar 20, 2017 at 14:32
  • 1
    \$\begingroup\$ @cliffroot should work for that case now \$\endgroup\$ Commented Mar 20, 2017 at 15:51
  • 1
    \$\begingroup\$ Nice includes trick. \$\endgroup\$ Commented Mar 20, 2017 at 18:08
4
\$\begingroup\$

JavaScript (ES6), 61 57 56 bytes

Takes the array of integers a and the expected sum s in currying syntax (a)(s). Returns a pair of matching integers as an array, or undefined if no such pair exists.

a=>s=>(r=a.find((b,i)=>a.some(c=>i--&&b+c==s)))&&[r,s-r]

Formatted and commented

a => // given an array of integers (a) s => ( // and an expected sum (s) r = a.find((b, i) => // look for b at position i in a such that: a.some(c => // there exists another c in a: i-- && // - at a different position b + c == s // - satisfying b + c == s ) // end of some() ) // end of find(): assign the result to r ) && // if it's not falsy: [r, s - r] // return the pair of integers

Test

let f = a=>s=>(r=a.find((b,i)=>a.some(c=>i--&&b+c==s)))&&[r,s-r] console.log(f([1,7,4,6,5,3,8,2])(8)) console.log(f([1,2,3,4])(8))

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 14 bytes

ŒcS=⁹$$ÐfḢṄo⁶H

Try it online!

This is a function (not a full program) that outputs to standard output. (The TIO link has a wrapper that runs a function and disregards its return value.)

This program could be 4 bytes shorter if not for the exit code requirement; returning an exit code of 1 in Jelly is fairly hard. (It's possible that there's a terser way to do this that I've missed.)

Explanation

ŒcS=⁹$$ÐfḢṄo⁶H Œc All pairs of values from {the first argument} Ðf Take only those which S=⁹ sum to {the second argument} $$ Parse the preceding three builtins as a group Ḣ Take the first result (0 if there are no results) Ṅ Output this result (plus a newline) on standard output o⁶ If this value is falsey, replace it with a space character H Halve every element of the value

We can halve every integer in a pair just fine, so the o⁶H will do nothing if we found a result, other than returning a useless return value that isn't relevant anyway (the Ṅ serves as a convenient single-byte method to determine the function's return value early, under PPCG rules). However, if we didn't find a result, we end up trying to halve a space character, an operation so meaningless it causes the Jelly interpreter to crash. Fortunately, this crash produces an exit code of 1.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Perl 5, 51 bytes

46 bytes of code + for 5 bytes for -pli flags.

$\="$_ $v"if$h{$v=$^I-$_};$h{$_}=1}{$\||exit 1

Try it online!

The idea is to iterate on the input list: on a number x ($_), if we previously saw n-x ($^I-$_) then we found what we were looking for, and set $\ to these two values ("$_ $v"). At the end, if $\ isn't set, then we exit 1, else it will be implicitly printed.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Does a literal tab work in place of the two characters ^I? \$\endgroup\$ Commented Mar 20, 2017 at 21:58
  • \$\begingroup\$ @ais523 It looks like I can't. Maybe it was possible on older versions of Perl though. \$\endgroup\$ Commented Mar 21, 2017 at 7:57
3
\$\begingroup\$

Röda, 60 56 bytes

f s,a{seq 1,s|{|x|[[x,s-x]]if[x in a,s-x in a-x]}_|pull}

Try it online!

This code throws an error if there is no answer. It generates all possible pairs that can form the sum s, ie. 1, s-1, 2, s-2, 3, s-3, ... Then it checks if both numbers are in the array a and if so, pushes them to the stream. pull reads one value from the stream and returns it. If there are no values in the stream, it throws an error. a-x returns the array a with x removed.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 2, 60 bytes

This short, until rules with exiting with code 1 are clarified. Now exits with error if nothing is found.

-5 bytes thanks to @Peilonrayz

-4 bytes thanks to @Rod

Try it online

a,s=input() while a: x=a.pop() if s-x in a:r=s-x,x print r
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ @Peilonrayz This would violate fith rule: two integers at different positions in list must be returned. (i.e. you can't return the same number from the same position twice) \$\endgroup\$ Commented Mar 20, 2017 at 15:59
  • 3
    \$\begingroup\$ You can use spaces+tabs for mixed indentation to reduce 2 bytes or switch to input() to reduce 4 bytes \$\endgroup\$ Commented Mar 20, 2017 at 18:54
  • \$\begingroup\$ input() automatically delivers the right type of object, not only strings? That's cool. \$\endgroup\$ Commented Mar 20, 2017 at 22:49
  • 2
    \$\begingroup\$ @Eric Duminil Yeah. It's equivalent to eval(raw_input()) (I think). \$\endgroup\$ Commented Mar 20, 2017 at 22:58
2
\$\begingroup\$

C++ 133 bytes (compiled with clang 4 and gcc 5.3 -std=c++14)

#include <set> auto f=[](auto s,int v,int&a,int&b){std::set<int>p;for(auto i:s)if(p.find(i)==end(p))p.insert(v-i);else{a=v-i;b=i;}};

C 108 bytes

void f(int*s,int*e,int v,int*a,int*b){do{int*n=s+1;do if(v-*s==*n){*a=*s;*b=*n;}while(++n<e);}while(++s<e);}
Improve this answer
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Welcome to the site! Unfortunately, I think you need to add 15 bytes for #include <set> and a few more for std::set. Although you can also save some bytes if you remove the braces around p.insert(v-i); \$\endgroup\$ Commented Mar 20, 2017 at 17:39
  • \$\begingroup\$ @DJMcMayhem oh, thank you. So should i include main()? \$\endgroup\$ Commented Mar 20, 2017 at 17:56
  • \$\begingroup\$ @em2er No, you don't need to include main. We consider (unless stated otherwise in the challenge) that a function is a valid submission. (welcome on the site btw!) \$\endgroup\$ Commented Mar 20, 2017 at 17:56
  • \$\begingroup\$ No, a function submission is fine. (And much shorter because you can take the input as arguments) You just need to count any includes that your submission requires. \$\endgroup\$ Commented Mar 20, 2017 at 18:00
  • 1
    \$\begingroup\$ @DJMcMayhem @Dada thanks a lot! i am not sure with end too, but it compiles on gcc without std:: (and set if course not) \$\endgroup\$ Commented Mar 20, 2017 at 18:05
2
\$\begingroup\$

Haskell, 34 bytes

(n:v)#s|elem(s-n)v=(n,s-n)|1<2=v#s

Try it online!

For each element of the list, this function checks if (sum-element) is in the following part of the list. Returns the first couple it finds. If the function reaches the end of the list it throws a "non -exhaustive patterns" error and exits with code 1.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'm afraid this approach does not work for inputs like [2,2]#4. \$\endgroup\$ Commented Mar 20, 2017 at 22:38
  • \$\begingroup\$ @Laikoni Thank you, I hadn't read the challenge well enough. This new version should be correct (and shorter^^) \$\endgroup\$ Commented Mar 21, 2017 at 0:12
2
\$\begingroup\$

PowerShell, 109 97 bytes

param($i,$a)($c=0..($a.count-1))|%{$c-ne($f=$_)|%{if($a[$f]+$a[$_]-eq$i){$a[$f,$_];exit}}};exit 1

Took a 12 byte deal that AdmBorkBork offered

Explanation

# Get the parameter passed where $i is the addition target from the array of numbers in $a param($i,$a) ($c=0..($a.count-1))|%{ # We are going to have two loops to process the array elements. # The first loop element will be held by $f $f=$_ # Create a second loop that will be the same as the first except for the position of $f to # prevent counting the same number twice. $c|?{$_-ne$f}|%{ # Check if the number at the current array indexes add to the target value. If so print and exit. if($a[$f]+$a[$_]-eq$i){$a[$f],$a[$_];exit} } } # If nothing was found in the loop then we just exit with error. exit 1

The current rules look for exit code which this does. Those could be removed and just check for numbers being returned and a falsy.

Sample Usage

If the code above was saved as function s

s 8 @(1,2,3,4) s 8 @(1,7,4,6,5,3,8,2)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can save a few more bytes by eliminating $c and looping downward -- ($a.count-1)..1|%{$f=$_;--$_..0|%{if... \$\endgroup\$ Commented Mar 21, 2017 at 20:12
2
\$\begingroup\$

R, 49 bytes

function(x,y){r=combn(x,2);r[,colSums(r)==y][,1]}

This finds all 2-combinations of x and returns a matrix. Then, sums by column and finds all the sums that equal to y (so without the [,1] part at the end it will print all the combinations that their sums equal to y)

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Japt, 9 bytes

Saved many bytes thanks to @ETHproductions

à2 æ_x ¥V

Try it online!

Explanation

à2 æ_x ¥V à2 // Creates all combinations of the input, length 2 æ // Returns the first item where: _x // The sum of the two items in each set ¥V // == Second input

Example

Input: [1,2,3], 4 à2 // [[1,2],[1,3],[2,3]] æ_x // [3, 4, 5 ] ¥V // 3!=4, 4==4 ✓ Output: // 1,3
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Javascript, 114 96 86 84 bytes

a=>b=>{c=b.length;for(x=0;x<c;x++)for( y=x;++y<c;)if(b[x]+b[y]==a)return[b[x],b[y]]}

Saved 1 byte thanks to @Cyoce and another 8 bytes thanks to @ETHProductions

This returns a tuple with the first combination of list-elements that sum up to the given input, or nothing for no match. I've removed the vars in the function; REPL.it crashes without them, but the Chrome Dev Console handles this just fine...

Try it online!

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Doesn't exit code 1, as the challenge specifically requests for invalid input. It's an invalid answer for now, but I've asked OP about this requirement for languages that can't do that easily. \$\endgroup\$ Commented Mar 20, 2017 at 14:26
  • \$\begingroup\$ @Matt Yes, that rule is observed: y=x+1 takes care of that. \$\endgroup\$ Commented Mar 20, 2017 at 15:29
  • 1
    \$\begingroup\$ You can use a=>b=>... to save a byte \$\endgroup\$ Commented Mar 20, 2017 at 19:18
  • 1
    \$\begingroup\$ You can save another three bytes with for(y=x;++y<b.length;){. Also, you can remove all sets of braces except the outermost one, and you can remove the space after return \$\endgroup\$ Commented Mar 23, 2017 at 12:39
1
\$\begingroup\$

Clojure, 77 bytes

#(first(mapcat(fn[i a](for[b(drop(inc i)%):when(=(+ a b)%2)][a b]))(range)%))

Returns the first such pair or nil.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 62 bytes

r=return;s#[]=r 1;s#(a:b)|elem(s-a)b=print(a,s-a)>>r 0|1<2=s#b

I still don't know what's allowed by the challenge and what not. I'm going for a function that prints a pair of numbers and returns 0 if there's a solution and prints nothing and returns 1 if there's no solution. As printing is I/O, I have to lift the return values into the IO-Monad (via return) and the actual type of the function is Num a => IO a.

Usage example (with return value printed by the repl):

*Main> 4 # [2,2] (2,2) 0

Try it online!.

If raising exceptions is allowed, fail will save some bytes (total 51):

s#[]=fail"";s#(a:b)|elem(s-a)b=print(a,s-a)|1<2=s#b
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 bytes

ŒcS=¥ÐfḢZ

Jelly has no way of setting the exit code to arbitrary values, so this produces a TypeError for input without a valid solution that will cause the parent interpreter to exit with exit code 1.

Try it online!

How it works

ŒcS=¥ÐfḢZ Main link. Argument: A (array of integers), n (integer) Œc Yield all 2-combinations of different elements of A. Ðf Filter by the link to the left. ¥ Combine the two links to the left into a dyadic chain. S Take the sum of the pair. = Compare the result with n. Ḣ Head; extract the first pair of the resulting array. This yields 0 if the array is empty. Z Zip/transpose the result. This doesn't (visibly) alter pairs, but it raise a TypeError for 0.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Nova, 101 bytes

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)}

One nice thing about code golf is that it helps me find bugs in my language. e.g. the space required between return and [y,x-y].

Once I add push/pop functions to Array.nova and fix return, would be 96 bytes:

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.pop())}))return[y,x-y];System.exit(1)}

Usage:

class Test { static q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)} public static main(String[] args) { Console.log(q([1, 2, 3, 4, 5], 8)) // [5, 3] Console.log(q([1, 2, 3, 4, 5], 5)) // [1, 4] Console.log(q([1, 2, 3, 4], 8)) // exit code 1 } }

Edit: Also, there's this way at 73 bytes (69 using pop), too:

q(Int[] a,Int x)=>[Int y=a.firstOrThrow({a.contains(x-a.remove(0))}),x-y]

firstOrThrow will throw an Exception, which will be uncaught and therefore ultimately exiting the program with exit code 1. ;)

This way seems more readable too.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 12 bytes

hfqsThQ.ceQ2

Explanation

 .ceQ2 Get all pairs from the second input fqsThQ Find the ones whose sum is the first input h Take the first (exits with error code 1 if there aren't any)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

PHP, 88 bytes

for($i=1;$a=$argv[$k=++$i];)for(;$b=$argv[++$k];)if($a+$b==$argv[1])die("$a $b");die(1);

takes input from command line arguments, sum first. Run with -nr.

Fortunately, die/ exit exits with 0 when you give it a string as parameter.

I tried to merge the loops to one; but it requires a longer initialization and test this time.

Improve this answer
\$\endgroup\$
1
0
\$\begingroup\$

Mathematica, 76 bytes

f::e="1";If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},Message@f::e,First@l]&

Fairly straightforward: #~Subsets~{2} gets all 2-element subsets of the list, then Cases[...,x_/;Tr@x==#2] picks only the ones whose sum is the number we want. If there are none of these, If[l=={}, Message@f::e,First@l] prints the error message f::e : 1 that we defined earlier (since I have no idea what else "exit status 1" might mean for Mathematica); otherwise, it returns the first entry in the list of pairs that sum to the correct thing.

If we're allowed to return a falsey value instead of doing that weird exit status thing, the following code has 58 bytes:

If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},1<0,First@l]&
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Scala, 55 41 bytes

(l,n)=>l combinations 2 find(_.sum==n)get

Returns a list of the two numbers if they exist and throws an error otherwise. Uncaught, this error will result in an exit status of 1.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Ruby, 53 48 bytes

->a,s{p(a.combination(2).find{|x,y|x+y==s})?0:1}

Input: a is the list, s is the expected sum.

If the 2 numbers are found, print them and return 0, otherwise return 1, as in the specification.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

TI-Basic, 59 bytes

Prompt L1 Prompt X While 1 L1(1→B seq(L1(C),C,2,dim(L1→L1 If sum(not(X-L1-B Then Disp B,X-B Return End End

Explanation:

Prompt L1 # 4 bytes, input array like "{1, 2, 3}" Prompt X # 3 bytes, Input target sum While 1 # 3 bytes, until the list is empty L1(1→B # 7 bytes, try the first element (now B) seq(L1(C),C,2,dim(L1→L1 # 18 bytes, remove first element from list If sum(not(X-L1-B # 10 bytes, if any element in the list plus B is the target Then # 2 bytes, then... Disp B,X-B # 7 bytes, print it and it's "complement" Return # 2 bytes, and exit gracefully End # 2 bytes End # 1 byte

If the program did not exit gracefully, it will cause an error when there are not enough elements in the list for it to continue.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 23 bytes

l~_,1>{e!2f<::+#)}{;;}?

Input is sum numbers. For example: 6 [3 2 3]. Leaves a positive number for truthy and an empty string or 0 for falsey.

Explanation:

l~ e# Read input and evaluate: | 7 [3 2 3] _ e# Duplicate: | 7 [3 2 3] [3 2 3] , e# Take the length: | 7 [3 2 3] 3 1>{ e# If more than 1: | 7 [3 2 3] e! e# Unique permutations: | 7 [[2 3 3] [3 2 3] [3 3 2]] 2f< e# Slice each to length 2: | 7 [[2 3] [3 2] [3 3]] ::+ e# Some each: | 7 [5 5 6] # e# Index: | -1 ) e# Increment: | 0 }{ e# Else: | 7 [3 2 3] ; e# Pop | 7 ; e# pop | }? e# Endif e# Implicit output: 0
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.