Anonymous user
Two sum: Difference between revisions
added =={{header|Pascal}}==
m (→{{header|zkl}}: sigh, should have stayed in bed) |
(added =={{header|Pascal}}==) |
||
Line 53:
{{out}}
<pre>[1,3]</pre>
=={{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.
<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
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[0] + A[1..Max] than A[1] + A[2..Max]...
//quadratic runtime (max-1)*max/ 2
var
i,j,tmpSum: NativeInt;
Begin
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i := low(A);
while i < High(A) do
Begin
tmpSum := Sum-a[i];
j := i+1;
while(j <= High(A)) do
begin
if tmpSum = a[j] then
Begin
Sol.SolRecI:=i;Sol.SolRecJ:=j;
result := true;
EXIT;
end;
inc(j);
end;
inc(i);
end;
result := false;
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;
result := false;
end;
var
Sol :tSolRec;
CheckArr : tMyArray;
MySum,i : NativeInt;
Begin
randomize;
setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1);
For i := 0 to SizeOf(ConstArray)-1 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,30000);
For i := High(CheckArr) downto 0 do
CheckArr[i] := 0;
CheckArr[High(CheckArr)-1] := 1;
CheckArr[High(CheckArr)] := 2;
MySum := 3;
//runtime 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>
{{out}}
<pre>[1,3] sum to 21
[29998,29999] sum to 3
[29998,29999] sum to 3
real 0m1.097s</pre>
=={{header|REXX}}==
<lang rexx>list=0 2 11 19 90
| |||