Two sum: Difference between revisions
Content added Content deleted
m (→{{header|zkl}}: sigh, should have stayed in bed) |
(added =={{header|Pascal}}==) |
||
Line 53: | Line 53: | ||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<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}}== |
=={{header|REXX}}== |
||
<lang rexx>list=0 2 11 19 90 |
<lang rexx>list=0 2 11 19 90 |