Two sum

Two sum is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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:

[0,3]

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

Translation of: zkl

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

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