Anonymous user
Two sum: Difference between revisions
m
→{{header|Pascal}}: checking High(A) was the most time consuming in function Check2SumUnSorted
(added =={{header|Pascal}}==) |
m (→{{header|Pascal}}: checking High(A) was the most time consuming in function Check2SumUnSorted) |
||
Line 54:
<pre>[1,3]</pre>
=={{header|Pascal}}==
A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 60000 elements that needs
<lang pascal>
program twosum;{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
sysutils;
Line 68 ⟶ 66:
tMyArray = array of NativeInt;
const
// just a gag using unusual index limits
ConstArray :array[-17..-13] of NativeInt = (0, 2, 11, 19, 90);
Line 73 ⟶ 72:
sum:NativeInt;
var Sol:tSolRec):boolean;
//Check every possible sum A[
//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) = is always 0 for dynamic array
var
i,j,tmpSum: NativeInt;
Line 80 ⟶ 82:
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i :=
while i
Begin
tmpSum :=
j := i
while
begin
if tmpSum = a[j] then
Begin
Sol.SolRecI:=
result := true;
EXIT;
end;
end;
end;
result := false;
Line 127 ⟶ 129:
dec(j);
end;
writeln(i:10,j:10);
result := false;
end;
Line 138 ⟶ 141:
randomize;
setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1);
For i :=
CheckArr[i] := ConstArray[i+low(ConstArray)];
Line 148 ⟶ 151:
//now test a bigger sorted array..
setlength(CheckArr,
For i := High(CheckArr) downto 0 do
CheckArr[i] :=
MySum := CheckArr[
writeln(#13#10,'Now checking array of ',length(CheckArr),
' elements',#13#10);
//runtime about 1 second▼
▲ //runtime 1 second
IF Check2SumUnSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
Line 166 ⟶ 168:
else
writeln('No solution found');
end.</lang>
</lang>▼
{{out}}
<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>▼
=={{header|REXX}}==
<lang rexx>list=0 2 11 19 90
| |||