Two sum
- Task
Given a sorted array of single positive integers, is it possible to find a pair of integers from that array that sum up to a given sum? If so, return indices of the two integers or an empty array if not.
- Example
Given numbers = [0, 2, 11, 19, 90], sum = 21,
Because numbers[1] + numbers[3] = 2 + 19 = 21,
return [1, 3].
- Source
Stack Overflow: Find pair of numbers in array that add to given sum
ALGOL 68
<lang algol68># returns the subscripts of a pair of numbers in a that sum to sum, a is assumed to be sorted #
- if there isn't a pair of numbers that summs to sum, an empty array is returned #
PRIO TWOSUM = 9; OP TWOSUM = ( []INT a, INT sum )[]INT:
BEGIN
BOOL found := FALSE;
INT i := LWB a;
INT j := UPB a;
WHILE i < j AND NOT found DO
INT s = a[ i ] + a[ j ];
IF s = sum THEN
found := TRUE
ELIF s < sum THEN
i +:= 1
ELSE
j -:= 1
FI
OD;
IF found THEN ( i, j ) ELSE () FI
END # TWOSUM # ;
- test the TWOSUM operator #
PROC print twosum = ( []INT a, INT sum )VOID:
BEGIN
[]INT pair = a[ AT 0 ] TWOSUM sum;
IF LWB pair > UPB pair THEN
# no pair with the required sum #
print( ( "[]", newline ) )
ELSE
# have a pair #
print( ( "[", whole( pair[ LWB pair ], 0 ), ", ", whole( pair[ UPB pair ], 0 ), "]", newline ) )
FI
END # print twosum # ;
print twosum( ( 0, 2, 11, 19, 90 ), 21 ); # should be [1, 3] # print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) # print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] # print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #</lang>
- Output:
[1, 3] [0, 6] [] [2, 3]
AppleScript
Nesting concatMap yields the cartesian product of the list with itself, and functions passed to map have access to the (1-based) array index in their second argument. Returning { } where the y index is lower than or equal to the x index ignores the 'lower triangle' of the cartesian grid, skipping mirror-image and duplicate number pairs. Returning { } where a sum condition is not met similarly acts as a filter – all of the empty lists in the map result are eliminated by the concat.
<lang AppleScript>-- summingPairIndices :: Int -> [Int] -> Int on summingPairIndices(n, xs)
script
-- productFilter :: [a] -> [b] -> a, b
on productFilter(xs, ys)
script product
on lambda(x, ix)
script filter
on lambda(y, iy)
if iy ≤ ix then
{} -- ignore - mirror-image pairs
else
if n = (x + y) then
-- Solution found, and
-- AppleScript indices are 1-based
Template:Ix - 1, iy - 1
else
{} -- eliminated from map by concat
end if
end if
end lambda
end script
concatMap(filter, ys)
end lambda
end script
concatMap(product, xs)
end productFilter
end script
result's productFilter(xs, xs)
end summingPairIndices
-- TEST
on run
summingPairIndices(21, [0, 2, 11, 19, 90]) --> Template:1, 3
end run
-- GENERIC LIBRARY FUNCTIONS
-- concatMap :: (a -> [b]) -> [a] -> [b] on concatMap(f, xs)
script append
on lambda(a, b)
a & b
end lambda
end script
foldl(append, {}, map(f, xs))
end concatMap
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to lambda(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to lambda(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then
f
else
script
property lambda : f
end script
end if
end mReturn</lang>
- Output:
<lang AppleScript>Template:1, 3</lang>
C#
<lang csharp>public static int[] TwoSum(int[] numbers, int sum) {
var map = new Dictionary<int, int>();
for (var i = 0; i < numbers.Length; i++)
{
var key = sum - numbers[i];
if (map.ContainsKey(key))
return new[] { map[key], i };
map.Add(numbers[i], i);
}
return Array.Empty<int>();
}</lang>
- Output:
[1,3]
Elixir
<lang elixir>defmodule RC do
def two_sum(numbers, sum) do
Enum.with_index(numbers) |>
Enum.reduce_while([], fn {x,i},acc ->
y = sum - x
case Enum.find_index(numbers, &(&1 == y)) do
nil -> {:cont, acc}
j -> {:halt, [i,j]}
end
end)
end
end
numbers = [0, 2, 11, 19, 90] IO.inspect RC.two_sum(numbers, 21) IO.inspect RC.two_sum(numbers, 25)</lang>
- Output:
[1, 3] []
FreeBASIC
<lang freebasic>' FB 1.05.0 Win64
' "a" is the array of sorted non-negative integers ' "b" is the array to contain the result and is assumed to be empty initially
Sub twoSum (a() As UInteger, b() As Integer, targetSum As UInteger)
Dim lb As Integer = LBound(a) Dim ub As Integer = UBound(a) If ub = -1 Then Return empty array Dim sum As UInteger
For i As Integer = lb To ub - 1
If a(i) <= targetSum Then
For j As Integer = i + 1 To ub
sum = a(i) + a(j)
If sum = targetSum Then
Redim b(0 To 1)
b(0) = i : b(1) = j
Return
ElseIf sum > targetSum Then
Exit For
End If
Next j
Else
Exit For
End If
Next i
End Sub
Dim a(0 To 4) As UInteger = {0, 2, 11, 19, 90} Dim b() As Integer Dim targetSum As UInteger = 21 twoSum a(), b(), targetSum If UBound(b) = -1 Then
Print "No two numbers were found whose sum is "; targetSum
Else
Print "The numbers with indices"; b(LBound(b)); " and"; b(UBound(b)); " sum to "; targetSum
End If Print Print "Press any number to quit" Sleep</lang>
- Output:
The numbers with indices 1 and 3 sum to 21
Haskell
<lang Haskell> twoSum::(Num a,Ord a) => a -> [a] -> [Int] twoSum num list = sol ls (reverse ls)
where
ls = zip list [0..]
sol [] _ = []
sol _ [] = []
sol xs@((x,i):us) ys@((y,j):vs) = ans
where
s = x + y
ans | s == num = [i,j]
| j <= i = []
| s < num = sol (dropWhile ((<num).(+y).fst) us) ys
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs
main = print $ twoSum 21 [0, 2, 11, 19, 90] </lang>
- Output:
[1,3]
Icon and Unicon
Icon and Unicon are ordinal languages, first index is one.
fullimag library used to pretty print lists.
<lang unicon>#
- twosum.icn, find two array elements that add up to a given sum
- Dedicated to the public domain
link fullimag procedure main(arglist)
sum := pop(arglist) | 21 L := [] if *arglist > 0 then every put(L, integer(!arglist)) & L := sort(L) else L := [0, 2, 11, 19, 90]
write(sum) write(fullimage(L)) write(fullimage(twosum(sum, L)))
end
- assume sorted list, only interested in zero or one solution
procedure twosum(sum, L)
i := 1
j := *L
while i < j do {
try := L[i] + L[j]
if try = sum then return [i,j]
else
if try < sum then
i +:= 1
else
j -:= 1
}
return []
end</lang>
- Output:
$ unicon -s twosum.icn -x 21 [0,2,11,19,90] [2,4]
J
So, first off, our basic approach will be to find the sums: <lang J> =+/~0 2 11 19 90
0 2 11 19 90 2 4 13 21 92
11 13 22 30 101 19 21 30 38 109 90 92 101 109 180</lang>
And, check if any of them are our desired value: <lang J> 21=+/~0 2 11 19 90 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0</lang>
Except, we want indices here, so let's toss the structure so we can get those: <lang J> ,21=+/~0 2 11 19 90 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
I.,21=+/~0 2 11 19 90
8 16</lang>
Except, we really needed that structure - in this case, since we had a five by five table, we want to interpret this result as a base five pair of numbers:
<lang J> $21=+/~0 2 11 19 90 5 5
5 5#:I.,21=+/~0 2 11 19 90
1 3 3 1</lang>
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: <lang J> ($ #: I.@,)21=+/~0 2 11 19 90 1 3 3 1</lang>
But to be more like the other task implementations here, we don't want all the results, we just want zero or one result. We can't just take the first result, though, because that would fill in a 0 0 result if there were none, and 0 0 could have been a valid result which does not make sense for the failure case. So, instead, let's package things up so we can add an empty to the end and take the first of those:
<lang J> ($ <@#: I.@,)21=+/~0 2 11 19 90 ┌───┬───┐ │1 3│3 1│ └───┴───┘
a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
┌───┬───┬┐ │1 3│3 1││ └───┴───┴┘
{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
┌───┐ │1 3│ └───┘
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
1 3</lang>
Finally, let's start pulling our arguments out using that three verbs combining form:
<lang J> ;{.a:,~($ <@#: I.@,) 21([ = +/~@])0 2 11 19 90 1 3
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90
1 3</lang>
a: is not a verb, but we can use a noun as the left verb of three as an implied constant verb whose result is itself: <lang J> ;{. 21 (a:,~ ($ <@#: I.@,)@([ = +/~@]))0 2 11 19 90 1 3</lang>
And, let's finish the job, give this a name, and test it out: <lang J> twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))
21 twosum 0 2 11 19 90
1 3</lang>
Except that looks like a bit of a mess. A lot of the reason for this is that ascii is ugly to look at. (Another issue, though, is that a lot of people are not used to architecting control flow as expressions.)
So... let's do this over again, using a more traditional implementation where we name intermediate results. (We're going to stick with our architecture, though, because changing the architecture to the more traditional approach would change the space/time tradeoff to require more time.)
<lang J>two_sum=:dyad define
sums=. +/~ y
matches=. x = sums
sum_inds=. I. , matches
pair_inds=. ($matches) #: sum_inds
; {. a: ,~ <"1 pair_inds
)</lang>
And, testing:
<lang J> 21 two_sum 0 2 11 19 90 1 3</lang>
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement:
<lang J>two_sum=:dyad define
sums=. +/~ y
matches=. x = sums
sum_inds=. I. , matches
pair_inds=. ($matches) #: sum_inds
if. #pair_inds do.
{.pair_inds
else.
i.0
end.
)</lang>
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:
<lang J>twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</lang>
Java
<lang java>import java.util.Arrays;
public class TwoSum {
public static void main(String[] args) {
long sum = 21;
int[] arr = {0, 2, 11, 19, 90};
System.out.println(Arrays.toString(twoSum(arr, sum))); }
public static int[] twoSum(int[] a, long target) {
int i = 0, j = a.length - 1;
while (i < j) {
long sum = a[i] + a[j];
if (sum == target)
return new int[]{i, j};
if (sum < target) i++;
else j--;
}
return null;
}
}</lang>
[1, 3]
JavaScript
ES5
Nesting concatMap yields the cartesian product of the list with itself, and functions passed to Array.map() have access to the array index in their second argument. Returning [] where the y index is lower than or equal to the x index ignores the 'lower triangle' of the cartesian grid, skipping mirror-image and duplicate number pairs. Returning [] where a sum condition is not met similarly acts as a filter – all of the empty lists in the map result are eliminated by the concat.
<lang JavaScript>(function () {
var concatMap = function (f, xs) {
return [].concat.apply([], xs.map(f))
};
return function (n, xs) {
return concatMap(function (x, ix) {
return concatMap(function (y, iy) {
return iy <= ix ? [] : x + y === n ? [
[ix, iy]
] : []
}, xs)
}, xs)
}(21, [0, 2, 11, 19, 90]);
})(); </lang>
- Output:
<lang JavaScript>1,3</lang>
ES6
First quickly composing a function from generic primitives like concatMap, cartesianProduct, nubBy.
<lang JavaScript>(() => {
'use strict';
let summingPairIndices = (n, xs) => nubBy(
([x, y], [x1, y1]) => x === x1 && y === y1,
concatMap(
([x, y]) =>
x === y ? [] : (x + y === n ? x, y : []),
cartesianProduct(xs, xs)
).map(xs => xs.sort())
).map(([x, y]) => [xs.indexOf(y), xs.indexOf(x)]);
// GENERIC LIBRARY FUNCTIONS
// concatMap :: (a -> [b]) -> [a] -> [b] let concatMap = (f, xs) => [].concat.apply([], xs.map(f)),
// cartesianProduct :: [a] -> [b] -> [(a, b)]
cartesianProduct = (xs, ys) =>
concatMap(x => concatMap(y => x, y, ys), xs),
// nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy = (p, xs) => {
let x = xs.length ? xs[0] : undefined;
return x !== undefined ? [x].concat(
nubBy(p, xs.slice(1).filter(y => !p(x, y)))
) : [];
};
return summingPairIndices(21, [0, 2, 11, 19, 90]);
})(); </lang>
- Output:
<lang JavaScript>[1,3]</lang>
and then fusing it down to something smaller and a little more efficient, expressed purely in terms of concatMap
<lang JavaScript>(() => {
'use strict';
// concatMap :: (a -> [b]) -> [a] -> [b] let concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// summingPairIndices :: -> Int -> [Int] -> [(Int, Int)] let summingPairIndices = (n, xs) =>
// Javascript map functions have access to the array index
// in their second argument.
concatMap((x, ix) => concatMap((y, iy) =>
iy <= ix ? [] : (// Ignoring mirror-image and duplicate tuples by
// skipping the 'lower triangle' (y <= x)
// of the cartesian product grid
x + y === n ? [
[ix, iy]
] : []
), xs), xs);
return summingPairIndices(21, [0, 2, 11, 19, 90]);
})(); </lang>
- Output:
<lang JavaScript>1,3</lang>
Lua
Lua uses one-based indexing. <lang lua>function twoSum (numbers, sum)
local i, j, s = 1, #numbers
while i < j do
s = numbers[i] + numbers[j]
if s == sum then
return {i, j}
elseif s < sum then
i = i + 1
else
j = j - 1
end
end
return {}
end
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</lang>
- Output:
2,4
ooRexx
<lang oorexx>a=.array~of(0, 2, 11, 19, 90) x=21 do i=1 To a~items
If a[i]>x Then Leave
Do j=i+1 To a~items
s=a[i]
s+=a[j]
Select
When s=x Then Leave i
When s>x Then Leave j
Otherwise Nop
End
End
End
If s=x Then Do
i-=1 /* array a's index starts with 1, so adjust */ j-=1 Say '['i','j']' End
Else
Say '[] - no items found'</lang>
- Output:
[1,3]
Pascal
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 83667 elements that needs 83667*86666/2 ~ 3.5 billion checks ( ~1 cpu-cycles/check, only if data in cache ). <lang pascal>program twosum; {$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} uses
sysutils;
type
tSolRec = record
SolRecI,
SolRecJ : NativeInt;
end;
tMyArray = array of NativeInt;
const // just a gag using unusual index limits
ConstArray :array[-17..-13] of NativeInt = (0, 2, 11, 19, 90);
function Check2SumUnSorted(const A :tMyArray;
sum:NativeInt;
var Sol:tSolRec):boolean;
//Check every possible sum A[max] + A[max-1..0] //than A[max-1] + A[max-2..0] etc pp. //quadratic runtime: maximal (max-1)*max/ 2 checks //High(A) always checked for dynamic array, even const //therefore run High(A) to low(A), which is always 0 for dynamic array label
SolFound;
var
i,j,tmpSum: NativeInt;
Begin
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i := High(A);
while i > low(A) do
Begin
tmpSum := sum-A[i];
j := i-1;
while j >= low(A) do
begin
//Goto is bad, but fast...
if tmpSum = a[j] Then
GOTO SolFound;
dec(j);
end;
dec(i);
end;
result := false;
exit;
SolFound:
Sol.SolRecI:=j;Sol.SolRecJ:=i; result := true;
end;
function Check2SumSorted(const A :tMyArray;
sum:NativeInt;
var Sol:tSolRec):boolean;
var
i,j,tmpSum: NativeInt;
Begin
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i := low(A);
j := High(A);
while(i < j) do
Begin
tmpSum := a[i] + a[j];
if tmpSum = sum then
Begin
Sol.SolRecI:=i;Sol.SolRecJ:=j;
result := true;
EXIT;
end;
if tmpSum < sum then
begin
inc(i);
continue;
end;
//if tmpSum > sum then
dec(j);
end;
writeln(i:10,j:10);
result := false;
end;
var
Sol :tSolRec; CheckArr : tMyArray; MySum,i : NativeInt;
Begin
randomize; setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1); For i := High(CheckArr) downto low(CheckArr) do CheckArr[i] := ConstArray[i+low(ConstArray)];
MySum := 21;
IF Check2SumSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
//now test a bigger sorted array..
setlength(CheckArr,83667);
For i := High(CheckArr) downto 0 do
CheckArr[i] := i;
MySum := CheckArr[Low(CheckArr)]+CheckArr[Low(CheckArr)+1];
writeln(#13#10,'Now checking array of ',length(CheckArr),
' elements',#13#10);
//runtime about 1 second
IF Check2SumUnSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
//runtime not measurable
IF Check2SumSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
end.</lang>
- Output:
[1,3] sum to 21 Now checking array of 83667 elements [0,1] sum to 1 [0,1] sum to 1 real 0m1.013s
Perl 6
<lang perl6>sub two_sum ( @numbers, $sum ) {
die '@numbers is not sorted' unless [<=] @numbers;
my ( $i, $j ) = 0, @numbers.end;
while $i < $j {
given $sum <=> @numbers[$i,$j].sum {
when Order::More { $i += 1 }
when Order::Less { $j -= 1 }
when Order::Same { return $i, $j }
}
}
return;
}
say two_sum ( 0, 2, 11, 19, 90 ), 21; say two_sum ( 0, 2, 11, 19, 90 ), 25;</lang>
- Output:
(1 3) Nil
REXX
<lang rexx>list=0 2 11 19 90 Do i=0 By 1 Until list=
Parse Var list a.i list End
n=i-1 x=21 do i=1 To n
If a.i>x Then Leave
Do j=i+1 To n
s=a.i
s=s+a.j
Select
When s=x Then Leave i
When s>x Then Leave j
Otherwise Nop
End
End
End
If s=x Then
Say '['i','j']'
Else
Say '[] - no items found'</lang>
- Output:
[1,3]
Ruby
<lang ruby>def two_sum(numbers, sum)
numbers.each_with_index do |x,i| if j = numbers.index(sum - x) then return [i,j] end end []
end
numbers = [0, 2, 11, 19, 90] p two_sum(numbers, 21) p two_sum(numbers, 25)</lang>
- Output:
[1, 3] []
When the size of the Array is bigger, the following is more suitable. <lang ruby>def two_sum(numbers, sum)
numbers.each_with_index do |x,i|
key = sum - x
if j = numbers.bsearch_index{|y| key<=>y}
return [i,j]
end
end
[]
end</lang>
Sidef
<lang ruby>func two_sum(numbers, sum) {
var (i, j) = (0, numbers.end)
while (i < j) {
given (sum <=> numbers[i]+numbers[j]) {
when (-1) { --j }
when (+1) { ++i }
default { return [i, j] }
}
}
return []
}
say two_sum([0, 2, 11, 19, 90], 21) say two_sum([0, 2, 11, 19, 90], 25)</lang>
- Output:
[1, 3] []
zkl
The sorted O(n) no external storage solution: <lang zkl>fcn twoSum(sum,ns){
i,j:=0,ns.len()-1;
while(i<j){
if((s:=ns[i] + ns[j]) == sum) return(i,j);
else if(s<sum) i+=1;
else if(s>sum) j-=1;
}
}</lang> <lang zkl>twoSum2(21,T(0,2,11,19,90)).println(); twoSum2(25,T(0,2,11,19,90)).println();</lang>
- Output:
L(1,3) False
The unsorted O(n!) all solutions solution: <lang zkl>fcn twoSum2(sum,ns){
Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum }) // lazy combos
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) })
}</lang> <lang zkl>twoSum2(21,T(0,2,11,19,90,21)).println(); twoSum2(25,T(0,2,11,19,90,21)).println();</lang>
- Output:
L(L(0,5),L(1,3)) L()