Find two integers from an unordered list to sum to the input

Question

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.

Answer 1

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

Answer 2

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)

Answer 3

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)

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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

Answer 10

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);}

Answer 11

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.

Answer 12

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) 

Answer 13

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)

Answer 14

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

Answer 15

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!

Answer 16

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.

Answer 17

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

Answer 18

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.

Answer 19

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.

Answer 20

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)

Answer 21

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

Answer 22

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]&

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

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