Two sum: Difference between revisions
m J: fi is for #!/bin/sh not for J, so fix that... |
→{{header|Java}}: added Java |
||
Line 134: | Line 134: | ||
<lang J>twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</lang> |
<lang J>twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</lang> |
||
=={{header|Java}}== |
|||
{{trans|Lua}} |
|||
<lang java>import java.util.Arrays; |
|||
public class TwoSum { |
|||
public static void main(String[] args) { |
|||
long sum = 13; |
|||
int[] arr = {0, 2, 11, 19, 90}; |
|||
System.out.println(Arrays.toString(twoSum(arr, sum))); |
|||
} |
|||
public static int[] twoSum(int[] a, long target) { |
|||
int i = 0, j = a.length - 1; |
|||
while (i < j) { |
|||
long sum = a[i] + a[j]; |
|||
if (sum == target) |
|||
return new int[]{i, j}; |
|||
if (sum < target) i++; |
|||
else j--; |
|||
} |
|||
return null; |
|||
} |
|||
}</lang> |
|||
<pre>[1, 3]</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
Revision as of 13:27, 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]
J
So, first off, our basic approach will be to find the sums: <lang J> =+/~0 2 11 19 90
0 2 11 19 90 2 4 13 21 92
11 13 22 30 101 19 21 30 38 109 90 92 101 109 180</lang>
And, check if any of them are our desired value: <lang J> 21=+/~0 2 11 19 90 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0</lang>
Except, we want indices here, so let's toss the structure so we can get those: <lang J> ,21=+/~0 2 11 19 90 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
I.,21=+/~0 2 11 19 90
8 16</lang>
Except, we really needed that structure - in this case, since we had a five by five table, we want to interpret this result as a base five pair of numbers:
<lang J> $21=+/~0 2 11 19 90 5 5
5 5#:I.,21=+/~0 2 11 19 90
1 3 3 1</lang>
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: <lang J> ($ #: I.@,)21=+/~0 2 11 19 90 1 3 3 1</lang>
But to be more like the other task implementations here, we don't want all the results, we just want zero or one result. We can't just take the first result, though, because that would fill in a 0 0 result if there were none, and 0 0 could have been a valid result which does not make sense for the failure case. So, instead, let's package things up so we can add an empty to the end and take the first of those:
<lang J> ($ <@#: I.@,)21=+/~0 2 11 19 90 ┌───┬───┐ │1 3│3 1│ └───┴───┘
a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
┌───┬───┬┐ │1 3│3 1││ └───┴───┴┘
{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
┌───┐ │1 3│ └───┘
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
1 3</lang>
Finally, let's start pulling our arguments out using that three verbs combining form:
<lang J> ;{.a:,~($ <@#: I.@,) 21([ = +/~@])0 2 11 19 90 1 3
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90
1 3</lang>
a: is not a verb, but we can use a noun as the left verb of three as an implied constant verb whose result is itself: <lang J> ;{. 21 (a:,~ ($ <@#: I.@,)@([ = +/~@]))0 2 11 19 90 1 3</lang>
And, let's finish the job, give this a name, and test it out: <lang J> twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))
21 twosum 0 2 11 19 90
1 3</lang>
Except that looks like a bit of a mess. A lot of the reason for this is that ascii is ugly to look at. (Another issue, though, is that a lot of people are not used to architecting control flow as expressions.)
So... let's do this over again, using a more traditional implementation where we name intermediate results. (We're going to stick with our architecture, though, because changing the architecture to the more traditional approach would change the space/time tradeoff to require more time.)
<lang J>two_sum=:dyad define
sums=. +/~ y matches=. x = sums sum_inds=. I. , matches pair_inds=. ($matches) #: sum_inds ; {. a: ,~ <"1 pair_inds
)</lang>
And, testing:
<lang J> 21 two_sum 0 2 11 19 90 1 3</lang>
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement:
<lang J>two_sum=:dyad define
sums=. +/~ y matches=. x = sums sum_inds=. I. , matches pair_inds=. ($matches) #: sum_inds if. #pair_inds do. {.pair_inds else. i.0 end.
)</lang>
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:
<lang J>twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</lang>
Java
<lang java>import java.util.Arrays;
public class TwoSum {
public static void main(String[] args) { long sum = 13; int[] arr = {0, 2, 11, 19, 90};
System.out.println(Arrays.toString(twoSum(arr, sum))); }
public static int[] twoSum(int[] a, long target) { int i = 0, j = a.length - 1; while (i < j) { long sum = a[i] + a[j]; if (sum == target) return new int[]{i, j}; if (sum < target) i++; else j--; } return null; }
}</lang>
[1, 3]
Lua
Lua uses one-based indexing. <lang lua>function twoSum (numbers, sum)
local i, j, s = 1, #numbers while i < j do s = numbers[i] + numbers[j] if s == sum then return {i, j} elseif s < sum then i = i + 1 else j = j - 1 end end return {}
end
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</lang>
- Output:
2,4
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.</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
Perl 6
<lang perl6>sub two_sum ( @numbers, $sum ) {
die '@numbers is not sorted' unless [<=] @numbers;
my ( $i, $j ) = 0, @numbers.end; while $i < $j { given $sum <=> @numbers[$i,$j].sum { when Order::More { $i += 1 } when Order::Less { $j -= 1 } when Order::Same { return $i, $j } } } return;
}
say two_sum ( 0, 2, 11, 19, 90 ), 21; say two_sum ( 0, 2, 11, 19, 90 ), 25;</lang>
- Output:
(1 3) Nil
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()