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.

\$\endgroup\$
  • 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\$ – Neil Mar 20 '17 at 11:55
  • 2
    \$\begingroup\$ In the example, why is the returned pair is (3,5) and not (1,7)? \$\endgroup\$ – Rod Mar 20 '17 at 12:09
  • 4
    \$\begingroup\$ How can there be a "first" pair in an unordered list? That's inherently self-contradictory. \$\endgroup\$ – Peter Taylor Mar 20 '17 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\$ – Rɪᴋᴇʀ Mar 20 '17 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\$ – Luis Mendo Mar 20 '17 at 18:06

26 Answers 26

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

\$\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)
\$\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)
\$\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));

\$\endgroup\$
  • \$\begingroup\$ The example was 3, 5 but this outputs 1, 7... \$\endgroup\$ – Neil Mar 20 '17 at 12:06
  • \$\begingroup\$ @Neil, sorry, i have amended rules because I messed up. 1,7 is ok. \$\endgroup\$ – philcolbourn Mar 20 '17 at 12:57
  • 1
    \$\begingroup\$ It won't work for f([2,2] 4) ? \$\endgroup\$ – cliffroot Mar 20 '17 at 14:32
  • 1
    \$\begingroup\$ @cliffroot should work for that case now \$\endgroup\$ – Tom Mar 20 '17 at 15:51
  • 1
    \$\begingroup\$ Nice includes trick. \$\endgroup\$ – Neil Mar 20 '17 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))

\$\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.

\$\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.

\$\endgroup\$
  • \$\begingroup\$ Does a literal tab work in place of the two characters ^I? \$\endgroup\$ – user62131 Mar 20 '17 at 21:58
  • \$\begingroup\$ @ais523 It looks like I can't. Maybe it was possible on older versions of Perl though. \$\endgroup\$ – Dada Mar 21 '17 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.

\$\endgroup\$
3
\$\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
\$\endgroup\$
  • \$\begingroup\$ @Peilonrayz Didn't realize that, thank you! \$\endgroup\$ – Dead Possum Mar 20 '17 at 15:54
  • \$\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\$ – Dead Possum Mar 20 '17 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\$ – Rod Mar 20 '17 at 18:54
  • \$\begingroup\$ @Rod Thanks! Input seems nicer \$\endgroup\$ – Dead Possum Mar 20 '17 at 19:50
  • 2
    \$\begingroup\$ @Eric Duminil Yeah. It's equivalent to eval(raw_input()) (I think). \$\endgroup\$ – Yytsi Mar 20 '17 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);}
\$\endgroup\$
  • 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\$ – DJMcMayhem Mar 20 '17 at 17:39
  • \$\begingroup\$ @DJMcMayhem oh, thank you. So should i include main()? \$\endgroup\$ – em2er Mar 20 '17 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\$ – Dada Mar 20 '17 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\$ – DJMcMayhem Mar 20 '17 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\$ – em2er Mar 20 '17 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.

\$\endgroup\$
  • \$\begingroup\$ I'm afraid this approach does not work for inputs like [2,2]#4. \$\endgroup\$ – Laikoni Mar 20 '17 at 22:38
  • \$\begingroup\$ @Laikoni Thank you, I hadn't read the challenge well enough. This new version should be correct (and shorter^^) \$\endgroup\$ – Leo Mar 21 '17 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) 
\$\endgroup\$
  • \$\begingroup\$ You can save a few more bytes by eliminating $c and looping downward -- ($a.count-1)..1|%{$f=$_;--$_..0|%{if... \$\endgroup\$ – AdmBorkBork Mar 21 '17 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)

\$\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
\$\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!

\$\endgroup\$
  • \$\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\$ – Rɪᴋᴇʀ Mar 20 '17 at 14:26
  • \$\begingroup\$ @Matt Yes, that rule is observed: y=x+1 takes care of that. \$\endgroup\$ – steenbergh Mar 20 '17 at 15:29
  • 1
    \$\begingroup\$ You can use a=>b=>... to save a byte \$\endgroup\$ – Cyoce Mar 20 '17 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\$ – ETHproductions Mar 23 '17 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.

\$\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
\$\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.
\$\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.

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

\$\endgroup\$
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]&
\$\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.

\$\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.

\$\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.

\$\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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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