Two sum: Difference between revisions
m (→{{header|Pascal}}: checking High(A) was the most time consuming in function Check2SumUnSorted) |
m (→{{header|Pascal}}: using GOTO to speed things up) |
||
Line 54: | Line 54: | ||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with |
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> |
<lang pascal>program twosum; |
||
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
|||
uses |
uses |
||
sysutils; |
sysutils; |
||
Line 68: | Line 68: | ||
// just a gag using unusual index limits |
// just a gag using unusual index limits |
||
ConstArray :array[-17..-13] of NativeInt = (0, 2, 11, 19, 90); |
ConstArray :array[-17..-13] of NativeInt = (0, 2, 11, 19, 90); |
||
function Check2SumUnSorted(const A :tMyArray; |
function Check2SumUnSorted(const A :tMyArray; |
||
sum:NativeInt; |
sum:NativeInt; |
||
Line 76: | Line 76: | ||
//quadratic runtime: maximal (max-1)*max/ 2 checks |
//quadratic runtime: maximal (max-1)*max/ 2 checks |
||
//High(A) always checked for dynamic array, even const |
//High(A) always checked for dynamic array, even const |
||
//therefore run High(A) to low(A) |
//therefore run High(A) to low(A), which is always 0 for dynamic array |
||
label |
|||
SolFound; |
|||
var |
var |
||
i,j,tmpSum: NativeInt; |
i,j,tmpSum: NativeInt; |
||
Line 85: | Line 87: | ||
while i > low(A) do |
while i > low(A) do |
||
Begin |
Begin |
||
tmpSum := sum- |
tmpSum := sum-A[i]; |
||
j := i-1; |
j := i-1; |
||
while j >= low(A) do |
while j >= low(A) do |
||
begin |
begin |
||
//Goto is bad, but fast... |
|||
if tmpSum = a[j] Then |
|||
GOTO SolFound; |
|||
result := true; |
|||
EXIT; |
|||
end; |
|||
dec(j); |
dec(j); |
||
end; |
end; |
||
Line 100: | Line 99: | ||
end; |
end; |
||
result := false; |
result := false; |
||
exit; |
|||
SolFound: |
|||
Sol.SolRecI:=j;Sol.SolRecJ:=i; |
|||
result := true; |
|||
end; |
end; |
||
Line 151: | Line 154: | ||
//now test a bigger sorted array.. |
//now test a bigger sorted array.. |
||
setlength(CheckArr, |
setlength(CheckArr,83667); |
||
For i := High(CheckArr) downto 0 do |
For i := High(CheckArr) downto 0 do |
||
CheckArr[i] := i; |
CheckArr[i] := i; |
||
Line 162: | Line 165: | ||
else |
else |
||
writeln('No solution found'); |
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. |
|||
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 |
//runtime not measurable |
||
IF Check2SumSorted(CheckArr,MySum,Sol) then |
IF Check2SumSorted(CheckArr,MySum,Sol) then |
||
Line 170: | Line 288: | ||
end.</lang> |
end.</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
[1,3] sum to 21 |
|||
Now checking array of |
Now checking array of 83667 elements |
||
[0,1] sum to 1 |
[0,1] sum to 1 |
||
[0,1] sum to 1 |
[0,1] sum to 1 |
||
real 0m1. |
real 0m1.013s</pre> |
||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 08:29, 5 October 2016
- 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]
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. 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
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()