Two sum: Difference between revisions

Content added Content deleted
(added =={{header|Pascal}}==)
m (→‎{{header|Pascal}}: checking High(A) was the most time consuming in function Check2SumUnSorted)
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 that needs 29999*30000/2 ~ 450 mio summations.
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 60000 elements that needs 59999*59998/2 ~ 1.8 billion checks ( ~2 cpu-cycles/check ).
<lang pascal>
<lang pascal>
program twosum;
program twosum;{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}

uses
uses
sysutils;
sysutils;
Line 68: Line 66:
tMyArray = array of NativeInt;
tMyArray = array of NativeInt;
const
const
// 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);
Line 73: Line 72:
sum:NativeInt;
sum:NativeInt;
var Sol:tSolRec):boolean;
var Sol:tSolRec):boolean;
//Check every possible sum A[0] + A[1..Max] than A[1] + A[2..Max]...
//Check every possible sum A[max] + A[max-1..0]
//than A[max-1] + A[max-2..0] etc pp.
//quadratic runtime (max-1)*max/ 2
//quadratic runtime: maximal (max-1)*max/ 2 checks
//High(A) always checked for dynamic array, even const
//therefore run High(A) to low(A) = is always 0 for dynamic array
var
var
i,j,tmpSum: NativeInt;
i,j,tmpSum: NativeInt;
Line 80: Line 82:
Sol.SolRecI:=0;
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
Sol.SolRecJ:=0;
i := low(A);
i := High(A);
while i < High(A) do
while i > low(A) do
Begin
Begin
tmpSum := Sum-a[i];
tmpSum := sum-a[i];
j := i+1;
j := i-1;
while(j <= High(A)) do
while j >= low(A) do
begin
begin
if tmpSum = a[j] then
if tmpSum = a[j] then
Begin
Begin
Sol.SolRecI:=i;Sol.SolRecJ:=j;
Sol.SolRecI:=j;Sol.SolRecJ:=i;
result := true;
result := true;
EXIT;
EXIT;
end;
end;
inc(j);
dec(j);
end;
end;
inc(i);
dec(i);
end;
end;
result := false;
result := false;
Line 127: Line 129:
dec(j);
dec(j);
end;
end;
writeln(i:10,j:10);
result := false;
result := false;
end;
end;
Line 138: Line 141:
randomize;
randomize;
setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1);
setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1);
For i := 0 to SizeOf(ConstArray)-1 do
For i := High(CheckArr) downto low(CheckArr) do
CheckArr[i] := ConstArray[i+low(ConstArray)];
CheckArr[i] := ConstArray[i+low(ConstArray)];


Line 148: Line 151:
//now test a bigger sorted array..
//now test a bigger sorted array..
setlength(CheckArr,30000);
setlength(CheckArr,60000);
For i := High(CheckArr) downto 0 do
For i := High(CheckArr) downto 0 do
CheckArr[i] := 0;
CheckArr[i] := i;
CheckArr[High(CheckArr)-1] := 1;
MySum := CheckArr[Low(CheckArr)]+CheckArr[Low(CheckArr)+1];
writeln(#13#10,'Now checking array of ',length(CheckArr),
CheckArr[High(CheckArr)] := 2;
' elements',#13#10);
⚫
//runtime about 1 second
MySum := 3;
⚫
//runtime 1 second
IF Check2SumUnSorted(CheckArr,MySum,Sol) then
IF Check2SumUnSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
Line 166: Line 168:
else
else
writeln('No solution found');
writeln('No solution found');
end.
end.</lang>
⚫
</lang>
{{out}}
{{out}}
<pre>[1,3] sum to 21
<pre>[1,3] sum to 21
⚫
[29998,29999] sum to 3
⚫
[29998,29999] sum to 3


Now checking array of 60000 elements
⚫
real 0m1.097s</pre>

⚫
[0,1] sum to 1
⚫
[0,1] sum to 1

⚫
real 0m1.035s
⚫
</pre>

=={{header|REXX}}==
=={{header|REXX}}==
<lang rexx>list=0 2 11 19 90
<lang rexx>list=0 2 11 19 90
Retrieved from "https://rosettacode.org/wiki/Two_sum"