Two sum: Difference between revisions
Metalosse12 (talk | contribs) No edit summary |
|||
(24 intermediate revisions by 19 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{Draft task|Arithmetic operations}} |
||
Line 22: | Line 22: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F two_sum(arr, num) |
||
V i = 0 |
V i = 0 |
||
V j = arr.len - 1 |
V j = arr.len - 1 |
||
Line 36: | Line 36: | ||
V numbers = [0, 2, 11, 19, 90] |
V numbers = [0, 2, 11, 19, 90] |
||
print(two_sum(numbers, 21)) |
print(two_sum(numbers, 21)) |
||
print(two_sum(numbers, 25))</ |
print(two_sum(numbers, 25))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 42: | Line 42: | ||
[1, 3] |
[1, 3] |
||
[] |
[] |
||
</pre> |
|||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }} |
|||
<syntaxhighlight lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
|||
/* program twosum64.s */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessResult: .asciz "Result : [" |
|||
szMessResult1: .asciz "," |
|||
szMessResult2: .asciz "]\n" |
|||
szMessStart: .asciz "Program 64 bits start.\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
szMessErreur: .asciz "No soluce ! \n" |
|||
tabArray: .quad 0, 2, 11, 19, 90 |
|||
.equ TABARRAYSIZE, (. - tabArray) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
sZoneConv1: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: // entry of program |
|||
ldr x0,qAdrszMessStart |
|||
bl affichageMess |
|||
ldr x0,qAdrtabArray |
|||
mov x1,#21 |
|||
bl rechTwoNumbers |
|||
cmp x0,#-1 // no soluce |
|||
beq 100f |
|||
mov x2,x1 |
|||
ldr x1,qAdrsZoneConv |
|||
bl conversion10 // decimal conversion |
|||
strb wzr,[x1,x0] |
|||
mov x0,x2 |
|||
ldr x1,qAdrsZoneConv1 |
|||
bl conversion10 // decimal conversion |
|||
strb wzr,[x1,x0] |
|||
mov x0,#5 // number string to display |
|||
ldr x1,qAdrszMessResult |
|||
ldr x2,qAdrsZoneConv // insert conversion in message |
|||
ldr x3,qAdrszMessResult1 |
|||
ldr x4,qAdrsZoneConv1 |
|||
ldr x5,qAdrszMessResult2 |
|||
stp x5,x4,[sp,-16]! // save registers |
|||
bl displayStrings // display message |
|||
add sp,sp,#16 |
|||
100: // standard end of the program |
|||
mov x0, #0 // return code |
|||
mov x8,EXIT |
|||
svc #0 // perform the system call |
|||
qAdrszCarriageReturn: .quad szCarriageReturn |
|||
qAdrsZoneConv: .quad sZoneConv |
|||
qAdrsZoneConv1: .quad sZoneConv1 |
|||
qAdrszMessResult: .quad szMessResult |
|||
qAdrszMessResult1: .quad szMessResult1 |
|||
qAdrszMessResult2: .quad szMessResult2 |
|||
qAdrszMessErreur: .quad szMessErreur |
|||
qAdrszMessStart: .quad szMessStart |
|||
qAdrtabArray: .quad tabArray |
|||
/******************************************************************/ |
|||
/* search two numbers to sum */ |
|||
/******************************************************************/ |
|||
/* x0 array addressr */ |
|||
/* x1 sum */ |
|||
/* x0 return first index */ |
|||
/* x1 return second index */ |
|||
rechTwoNumbers: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
stp x5,x6,[sp,-16]! // save registers |
|||
stp x7,x8,[sp,-16]! // save registers |
|||
mov x3,#0 // init result |
|||
1: // loop |
|||
ldr x4,[x0,x3,lsl #3] // load first number |
|||
mov x5,x3 // indice2 |
|||
2: |
|||
ldr x6,[x0,x5,lsl #3] // load 2th number |
|||
add x7,x6,x4 // add the two numbers |
|||
cmp x7,x1 // equal to origin |
|||
beq 3f // yes -> ok |
|||
add x5,x5,#1 // increment indice2 |
|||
cmp x5,#TABARRAYSIZE // end ? |
|||
blt 2b // no -> loop |
|||
add x3,x3,#1 // increment indice1 |
|||
cmp x3,#TABARRAYSIZE - 1 // end ? |
|||
blt 1b // no loop |
|||
// not found |
|||
ldr x0,qAdrszMessErreur |
|||
bl affichageMess |
|||
mov x0,#-1 |
|||
mov x1,#-1 |
|||
b 100f // end |
|||
3: |
|||
mov x0,x3 // return results |
|||
mov x1,x5 |
|||
100: |
|||
ldp x7,x8,[sp],16 // restaur registers |
|||
ldp x5,x6,[sp],16 // restaur registers |
|||
ldp x3,x4,[sp],16 // restaur registers |
|||
ldp x2,lr,[sp],16 // restaur registers |
|||
ret |
|||
/***************************************************/ |
|||
/* display multi strings */ |
|||
/***************************************************/ |
|||
/* x0 contains number strings address */ |
|||
/* x1 address string1 */ |
|||
/* x2 address string2 */ |
|||
/* x3 address string3 */ |
|||
/* other address on the stack */ |
|||
/* thinck to add number other address * 4 to add to the stack */ |
|||
displayStrings: // INFO: displayStrings |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
add fp,sp,#48 // save paraméters address (6 registers saved * 8 bytes) |
|||
mov x4,x0 // save strings number |
|||
cmp x4,#0 // 0 string -> end |
|||
ble 100f |
|||
mov x0,x1 // string 1 |
|||
bl affichageMess |
|||
cmp x4,#1 // number > 1 |
|||
ble 100f |
|||
mov x0,x2 |
|||
bl affichageMess |
|||
cmp x4,#2 |
|||
ble 100f |
|||
mov x0,x3 |
|||
bl affichageMess |
|||
cmp x4,#3 |
|||
ble 100f |
|||
mov x3,#3 |
|||
sub x2,x4,#4 |
|||
1: // loop extract address string on stack |
|||
ldr x0,[fp,x2,lsl #3] |
|||
bl affichageMess |
|||
subs x2,x2,#1 |
|||
bge 1b |
|||
100: |
|||
ldp x4,x5,[sp],16 // restaur registers |
|||
ldp x2,x3,[sp],16 // restaur registers |
|||
ldp x1,lr,[sp],16 // restaur registers |
|||
ret |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
.include "../includeARM64.inc" |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Program 64 bits start. |
|||
Result : [1,3] |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT len) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO len-1 |
|||
DO |
|||
PrintI(a(i)) |
|||
IF i<len-1 THEN |
|||
Put(' ) |
|||
FI |
|||
OD |
|||
Put(']) PutE() |
|||
RETURN |
|||
PROC PrintPairs(INT ARRAY a INT len,sum) |
|||
INT i,j,p1,p2,s,count |
|||
count=0 |
|||
FOR i=0 TO len-2 |
|||
DO |
|||
p1=a(i) |
|||
FOR j=i+1 TO len-1 |
|||
DO |
|||
p2=a(j) |
|||
s=p1+p2 |
|||
IF s=sum THEN |
|||
PrintF("(%I,%I) ",i,j) |
|||
count==+1 |
|||
ELSEIF s>sum THEN |
|||
EXIT |
|||
FI |
|||
OD |
|||
OD |
|||
IF count=0 THEN |
|||
Print("none") |
|||
FI |
|||
PutE() |
|||
RETURN |
|||
PROC Test(INT ARRAY a INT len,sum) |
|||
Print("Array: ") PrintArray(a,len) |
|||
Print("Sum: ") PrintIE(sum) |
|||
Print("Pairs: ") PrintPairs(a,len,sum) |
|||
PutE() |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY a=[0 2 11 19 90] |
|||
INT ARRAY b=[0 2 3 3 4 11 17 17 18 19 90] |
|||
Test(a,5,21) |
|||
Test(a,5,22) |
|||
Test(b,11,21) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Two_sum.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array: [0 2 11 19 90] |
|||
Sum: 21 |
|||
Pairs: (1,3) |
|||
Array: [0 2 11 19 90] |
|||
Sum: 22 |
|||
Pairs: none |
|||
Array: [0 2 3 3 4 11 17 17 18 19 90] |
|||
Sum: 21 |
|||
Pairs: (1,9) (2,8) (3,8) (4,6) (4,7) |
|||
</pre> |
</pre> |
||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">integer i, u, v; |
||
index x; |
index x; |
||
list l; |
list l; |
||
Line 57: | Line 295: | ||
break; |
break; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>1 3</pre> |
<pre>1 3</pre> |
||
Line 63: | Line 301: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{trans|Lua}} |
{{trans|Lua}} |
||
< |
<syntaxhighlight lang="algol68"># returns the subscripts of a pair of numbers in a that sum to sum, a is assumed to be sorted # |
||
# if there isn't a pair of numbers that summs to sum, an empty array is returned # |
# if there isn't a pair of numbers that summs to sum, an empty array is returned # |
||
PRIO TWOSUM = 9; |
PRIO TWOSUM = 9; |
||
Line 99: | Line 337: | ||
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) # |
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) # |
||
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] # |
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] # |
||
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #</ |
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 119: | Line 357: | ||
Then, we just need to find where the right argument (the target) is equal to the matrix, get the indices, and return the first one (⊃). |
Then, we just need to find where the right argument (the target) is equal to the matrix, get the indices, and return the first one (⊃). |
||
<syntaxhighlight lang="apl"> |
|||
<lang APL> |
|||
⎕io ← 0 ⍝ sets index origin to 0 |
⎕io ← 0 ⍝ sets index origin to 0 |
||
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺} |
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺} |
||
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3 |
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 141: | Line 379: | ||
AppleScript, unusually, happens to make internal use of one-based indices, rigid adherence to which would, of course, in this case, simply produce the wrong result :-) |
AppleScript, unusually, happens to make internal use of one-based indices, rigid adherence to which would, of course, in this case, simply produce the wrong result :-) |
||
< |
<syntaxhighlight lang="applescript">-------------------------- TWO SUM ------------------------- |
||
-- twoSum :: Int -> [Int] -> [(Int, Int)] |
-- twoSum :: Int -> [Int] -> [(Int, Int)] |
||
Line 287: | Line 525: | ||
end repeat |
end repeat |
||
return lst |
return lst |
||
end zip</ |
end zip</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<lang |
<syntaxhighlight lang="applescript">{{1, 3}}</syntaxhighlight> |
||
---- |
---- |
||
Line 295: | Line 533: | ||
Like the "Functional" script above, this returns multiple solutions when they're found. However it assumes a sorted list, as per the clarified task description, which allows some optimisation of the search. Also, the indices returned are 1-based, which is the AppleScript norm. |
Like the "Functional" script above, this returns multiple solutions when they're found. However it assumes a sorted list, as per the clarified task description, which allows some optimisation of the search. Also, the indices returned are 1-based, which is the AppleScript norm. |
||
< |
<syntaxhighlight lang="applescript">on twoSum(givenNumbers, givenSum) |
||
script o |
script o |
||
property lst : givenNumbers |
property lst : givenNumbers |
||
Line 320: | Line 558: | ||
twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list. |
twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list. |
||
twoSum({0, 3, 11, 19, 90}, 21) -- No matches. |
twoSum({0, 3, 11, 19, 90}, 21) -- No matches. |
||
twoSum({-44, 0, 0, 2, 10, 11, 19, 21, 21, 21, 65, 90}, 21) -- Multiple solutions.</ |
twoSum({-44, 0, 0, 2, 10, 11, 19, 21, 21, 21, 65, 90}, 21) -- Multiple solutions.</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight lang="applescript">{{2, 4}} |
||
{} |
{} |
||
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</ |
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</syntaxhighlight> |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<syntaxhighlight lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program twosum.s */ |
|||
/* REMARK 1 : this program use routines in a include file |
|||
see task Include a file language arm assembly |
|||
for the routine affichageMess conversion10 |
|||
see at end of this program the instruction include */ |
|||
/* for constantes see task include a file in arm assembly */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
.include "../constantes.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessResult: .asciz "Result : [" |
|||
szMessResult1: .asciz "," |
|||
szMessResult2: .asciz "]\n" |
|||
szMessStart: .asciz "Program 32 bits start.\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
szMessErreur: .asciz "No soluce ! \n" |
|||
tabArray: .int 0, 2, 11, 19, 90 |
|||
.equ TABARRAYSIZE, (. - tabArray) / 4 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
sZoneConv1: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: @ entry of program |
|||
ldr r0,iAdrszMessStart |
|||
bl affichageMess |
|||
ldr r0,iAdrtabArray |
|||
mov r1,#21 |
|||
bl rechTwoNumbers |
|||
cmp r0,#-1 @ no soluce |
|||
beq 100f |
|||
mov r2,r1 |
|||
ldr r1,iAdrsZoneConv |
|||
bl conversion10 @ decimal conversion |
|||
mov r3,#0 |
|||
strb r3,[r1,r0] |
|||
mov r0,r2 |
|||
ldr r1,iAdrsZoneConv1 |
|||
bl conversion10 @ decimal conversion |
|||
mov r3,#0 |
|||
strb r3,[r1,r0] |
|||
mov r0,#5 @ number string to display |
|||
ldr r1,iAdrszMessResult |
|||
ldr r2,iAdrsZoneConv @ insert conversion in message |
|||
ldr r3,iAdrszMessResult1 |
|||
ldr r4,iAdrsZoneConv1 |
|||
push {r4} |
|||
ldr r4,iAdrszMessResult2 |
|||
push {r4} |
|||
bl displayStrings @ display message |
|||
add sp,#8 |
|||
100: @ standard end of the program |
|||
mov r0, #0 @ return code |
|||
mov r7, #EXIT @ request to exit program |
|||
svc #0 @ perform the system call |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrsZoneConv: .int sZoneConv |
|||
iAdrsZoneConv1: .int sZoneConv1 |
|||
iAdrszMessResult: .int szMessResult |
|||
iAdrszMessResult1: .int szMessResult1 |
|||
iAdrszMessResult2: .int szMessResult2 |
|||
iAdrszMessErreur: .int szMessErreur |
|||
iAdrszMessStart: .int szMessStart |
|||
iAdrtabArray: .int tabArray |
|||
/******************************************************************/ |
|||
/* search two numbers from sum */ |
|||
/******************************************************************/ |
|||
/* r0 array addressr */ |
|||
/* r1 sum */ |
|||
/* r0 return fist index */ |
|||
/* r1 return second index */ |
|||
rechTwoNumbers: |
|||
push {r2-r7,lr} @ save registers |
|||
mov r3,#0 @ init result |
|||
1: @ loop |
|||
ldr r4,[r0,r3,lsl #2] @ load first number |
|||
mov r5,r3 @ indice2 |
|||
2: |
|||
ldr r6,[r0,r5,lsl #2] @ load 2th number |
|||
add r7,r6,r4 @ add the two numbers |
|||
cmp r7,r1 @ equal to origin |
|||
beq 3f @ yes -> ok |
|||
add r5,r5,#1 @ increment indice2 |
|||
cmp r5,#TABARRAYSIZE @ end ? |
|||
blt 2b @ no -> loop |
|||
add r3,r3,#1 @ increment indice1 |
|||
cmp r3,#TABARRAYSIZE - 1 @ end ? |
|||
blt 1b @ no loop |
|||
@ not found |
|||
ldr r0,iAdrszMessErreur |
|||
bl affichageMess |
|||
mov r0,#-1 |
|||
mov r1,#-1 |
|||
b 100f @ end |
|||
3: |
|||
mov r0,r3 @ return results |
|||
mov r1,r5 |
|||
100: |
|||
pop {r2-r7,pc} |
|||
/***************************************************/ |
|||
/* display multi strings */ |
|||
/***************************************************/ |
|||
/* r0 contains number strings address */ |
|||
/* r1 address string1 */ |
|||
/* r2 address string2 */ |
|||
/* r3 address string3 */ |
|||
/* other address on the stack */ |
|||
/* thinck to add number other address * 4 to add to the stack */ |
|||
displayStrings: @ INFO: displayStrings |
|||
push {r1-r4,fp,lr} @ save des registres |
|||
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes) |
|||
mov r4,r0 @ save strings number |
|||
cmp r4,#0 @ 0 string -> end |
|||
ble 100f |
|||
mov r0,r1 @ string 1 |
|||
bl affichageMess |
|||
cmp r4,#1 @ number > 1 |
|||
ble 100f |
|||
mov r0,r2 |
|||
bl affichageMess |
|||
cmp r4,#2 |
|||
ble 100f |
|||
mov r0,r3 |
|||
bl affichageMess |
|||
cmp r4,#3 |
|||
ble 100f |
|||
mov r3,#3 |
|||
sub r2,r4,#4 |
|||
1: @ loop extract address string on stack |
|||
ldr r0,[fp,r2,lsl #2] |
|||
bl affichageMess |
|||
subs r2,#1 |
|||
bge 1b |
|||
100: |
|||
pop {r1-r4,fp,pc} |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
.include "../affichage.inc" |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Program 32 bits start. |
|||
Result : [1,3] |
|||
</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">twoSum: function [numbers, s][ |
|||
loop.with:'i numbers 'x [ |
|||
if not? null? j: <= index numbers s-x -> |
|||
return @[i j] |
|||
] |
|||
return [] |
|||
] |
|||
nums: [0 2 11 19 90] |
|||
print ["twoSum 21:" twoSum nums 21] |
|||
print ["twoSum 25:" twoSum nums 25]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>twoSum 21: [1 3] |
|||
twoSum 25: []</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">TwoSum(a, target){ |
||
i := 1, j := a.MaxIndex() |
i := 1, j := a.MaxIndex() |
||
while(i < j){ |
while(i < j){ |
||
Line 339: | Line 761: | ||
} |
} |
||
return "not found" |
return "not found" |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">MsgBox % TwoSum([0, 2, 11, 19, 90], 21) ; returns 2, 4 (first index is 1 not 0)</syntaxhighlight> |
||
Outputs:<pre>2,4</pre> |
Outputs:<pre>2,4</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f TWO_SUM.AWK |
# syntax: GAWK -f TWO_SUM.AWK |
||
BEGIN { |
BEGIN { |
||
Line 369: | Line 791: | ||
return("[]") |
return("[]") |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 377: | Line 799: | ||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
< |
<syntaxhighlight lang="befunge">>000pv |
||
>&:0\`#v_00g:1+00p6p |
>&:0\`#v_00g:1+00p6p |
||
v >$&50p110p020p |
v >$&50p110p020p |
||
Line 392: | Line 814: | ||
>:#,_@ 8 |
>:#,_@ 8 |
||
p |
p |
||
> ^</ |
> ^</syntaxhighlight> |
||
There are a couple of caveats due to limitations of the language. The target cannot be above 127, there can be no more than 47 elements in the list and the list must be delimited by a negative number before the target value as follows: |
There are a couple of caveats due to limitations of the language. The target cannot be above 127, there can be no more than 47 elements in the list and the list must be delimited by a negative number before the target value as follows: |
||
<pre> |
<pre> |
||
Line 402: | Line 824: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdio.h> |
#include<stdio.h> |
||
Line 424: | Line 846: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
<pre> |
<pre> |
||
Line 431: | Line 853: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 463: | Line 885: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>1, 3</pre> |
<pre>1, 3</pre> |
||
Line 469: | Line 891: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <map> |
#include <map> |
||
#include <tuple> |
#include <tuple> |
||
Line 503: | Line 925: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1,3}</pre> |
<pre>{1,3}</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
void main() { |
void main() { |
||
Line 545: | Line 967: | ||
return []; |
return []; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 3]</pre> |
<pre>[1, 3]</pre> |
||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
<lang> |
<syntaxhighlight lang="text"> |
||
main() { |
main() { |
||
var a = [1,2,3,4,5]; |
var a = [1,2,3,4,5]; |
||
Line 579: | Line 1,001: | ||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
{{libheader| System.SysUtils}} |
{{libheader| System.SysUtils}} |
||
{{libheader| System.Generics.Collections}} |
{{libheader| System.Generics.Collections}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
<syntaxhighlight lang="delphi"> |
|||
<lang Delphi> |
|||
program Two_Sum; |
program Two_Sum; |
||
Line 621: | Line 1,043: | ||
Writeln('(', i, ',', j, ')'); |
Writeln('(', i, ',', j, ')'); |
||
Readln; |
Readln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
(1,3) |
(1,3) |
||
</pre> |
</pre> |
||
=={{header|EasyLang}}== |
|||
EasyLang arrays are one-based, so the indices returned are also one-based. |
|||
<syntaxhighlight lang="easylang"> |
|||
proc twoSum sum . array[] pair[] . |
|||
i = 1 |
|||
j = len array[] |
|||
pair[] = [ ] |
|||
repeat |
|||
if array[i] + array[j] = sum |
|||
pair[] = [ i j ] |
|||
return |
|||
elif array[i] + array[j] > sum |
|||
j -= 1 |
|||
elif array[i] + array[j] < sum |
|||
i += 1 |
|||
. |
|||
until i = j |
|||
. |
|||
. |
|||
numbers[] = [ 0 2 11 19 90 ] |
|||
twoSum 21 numbers[] pair[] |
|||
print pair[] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 2 4]</pre> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def two_sum(numbers, sum) do |
def two_sum(numbers, sum) do |
||
Enum.with_index(numbers) |> |
Enum.with_index(numbers) |> |
||
Line 642: | Line 1,091: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
IO.inspect RC.two_sum(numbers, 21) |
IO.inspect RC.two_sum(numbers, 21) |
||
IO.inspect RC.two_sum(numbers, 25)</ |
IO.inspect RC.two_sum(numbers, 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 651: | Line 1,100: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Two Sum : Nigel Galloway December 5th., 2017 |
// Two Sum : Nigel Galloway December 5th., 2017 |
||
let fN n i = |
let fN n i = |
||
Line 662: | Line 1,111: | ||
fN n 0 |
fN n 0 |
||
printfn "%A" (fN [0; 2; 11; 19; 90] 21) |
printfn "%A" (fN [0; 2; 11; 19; 90] 21) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 669: | Line 1,118: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: combinators fry kernel locals math prettyprint sequences ; |
||
IN: rosetta-code.two-sum |
IN: rosetta-code.two-sum |
||
Line 682: | Line 1,131: | ||
x y = { } { x y } ? ; |
x y = { } { x y } ? ; |
||
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each</ |
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 689: | Line 1,138: | ||
{ 0 2 } |
{ 0 2 } |
||
</pre> |
</pre> |
||
A version that maintains a point-free style while still iterating over the numbers once: |
|||
<syntaxhighlight lang="factor">USING: accessors arrays assocs combinators.extras hashtables |
|||
kernel math math.combinatorics sequences ; |
|||
IN: rosetta-code.two-sum |
|||
DEFER: (two-sum) |
|||
TUPLE: helper sum seq index hash ; |
|||
: <two-sum-helper> ( sum seq -- helper ) |
|||
\ helper new |
|||
swap [ >>seq ] keep length <hashtable> >>hash |
|||
swap >>sum 0 >>index ; |
|||
: no-sum ( helper -- empty ) drop { } ; |
|||
: in-bounds? ( helper -- ? ) |
|||
[ index>> ] [ seq>> length ] bi < ; |
|||
: next-sum ( helper -- pair ) |
|||
dup in-bounds? [ (two-sum) ] [ no-sum ] if ; |
|||
: next-index ( helper -- helper ) [ 1 + ] change-index ; |
|||
: result ( helper index -- helper ) swap index>> 2array ; |
|||
: find-compliment-index ( helper -- helper index/f ) |
|||
dup [ sum>> ] [ index>> ] [ seq>> nth - ] [ ] quad hash>> at ; |
|||
: remember-item ( helper -- helper ) |
|||
dup [ hash>> ] [ index>> ] [ seq>> nth ] [ index>> ] |
|||
quad set-of drop ; |
|||
: (two-sum) ( helper -- pair ) |
|||
remember-item find-compliment-index |
|||
[ result ] [ next-index next-sum ] if* ; |
|||
: two-sum ( sum seq -- pair ) <two-sum-helper> (two-sum) ; |
|||
MAIN: [ { 21 55 11 } [ { 0 2 11 19 90 } two-sum . ] each ] |
|||
</syntaxhighlight> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|Gforth|0.7.3}} |
{{works with|Gforth|0.7.3}} |
||
< |
<syntaxhighlight lang="forth">CREATE A CELL ALLOT |
||
: A[] ( n -- A[n]) CELLS A @ + @ ; |
: A[] ( n -- A[n]) CELLS A @ + @ ; |
||
:NONAME 1- ; |
:NONAME 1- ; |
||
Line 715: | Line 1,206: | ||
TEST1 3 TWOSUM CR |
TEST1 3 TWOSUM CR |
||
TEST1 8 TWOSUM CR |
TEST1 8 TWOSUM CR |
||
BYE</ |
BYE</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 3] |
<pre>[1, 3] |
||
Line 723: | Line 1,214: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
< |
<syntaxhighlight lang="fortran">program twosum |
||
implicit none |
implicit none |
||
Line 748: | Line 1,239: | ||
end program twosum |
end program twosum |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 754: | Line 1,245: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
' "a" is the array of sorted non-negative integers |
' "a" is the array of sorted non-negative integers |
||
Line 794: | Line 1,285: | ||
Print |
Print |
||
Print "Press any number to quit" |
Print "Press any number to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 803: | Line 1,294: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 839: | Line 1,330: | ||
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum) |
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 848: | Line 1,339: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
====Returning first match==== |
====Returning first match==== |
||
< |
<syntaxhighlight lang="haskell">twoSum::(Num a,Ord a) => a -> [a] -> [Int] |
||
twoSum num list = sol ls (reverse ls) |
twoSum num list = sol ls (reverse ls) |
||
where |
where |
||
Line 862: | Line 1,353: | ||
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs |
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs |
||
main = print $ twoSum 21 [0, 2, 11, 19, 90]</ |
main = print $ twoSum 21 [0, 2, 11, 19, 90]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
Line 869: | Line 1,360: | ||
Listing multiple solutions (as zero-based indices) where they exist: |
Listing multiple solutions (as zero-based indices) where they exist: |
||
< |
<syntaxhighlight lang="haskell">sumTo :: Int -> [Int] -> [(Int, Int)] |
||
sumTo n ns = |
sumTo n ns = |
||
let ixs = zip [0 ..] ns |
let ixs = zip [0 ..] ns |
||
Line 882: | Line 1,373: | ||
main :: IO () |
main :: IO () |
||
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</ |
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</syntaxhighlight> |
||
Or, resugaring a little – pulling more into the scope of the list comprehension: |
Or, resugaring a little – pulling more into the scope of the list comprehension: |
||
< |
<syntaxhighlight lang="haskell">sumTo :: Int -> [Int] -> [(Int, Int)] |
||
sumTo n ns = |
sumTo n ns = |
||
let ixs = zip [0 ..] ns |
let ixs = zip [0 ..] ns |
||
Line 894: | Line 1,385: | ||
main :: IO () |
main :: IO () |
||
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</ |
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>(1,3) |
<pre>(1,3) |
||
Line 905: | Line 1,396: | ||
<tt>fullimag</tt> library used to pretty print lists. |
<tt>fullimag</tt> library used to pretty print lists. |
||
< |
<syntaxhighlight lang="unicon"># |
||
# twosum.icn, find two array elements that add up to a given sum |
# twosum.icn, find two array elements that add up to a given sum |
||
# Dedicated to the public domain |
# Dedicated to the public domain |
||
Line 935: | Line 1,426: | ||
} |
} |
||
return [] |
return [] |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 947: | Line 1,438: | ||
So, first off, our basic approach will be to find the sums: |
So, first off, our basic approach will be to find the sums: |
||
< |
<syntaxhighlight lang="j"> =+/~0 2 11 19 90 |
||
0 2 11 19 90 |
0 2 11 19 90 |
||
2 4 13 21 92 |
2 4 13 21 92 |
||
11 13 22 30 101 |
11 13 22 30 101 |
||
19 21 30 38 109 |
19 21 30 38 109 |
||
90 92 101 109 180</ |
90 92 101 109 180</syntaxhighlight> |
||
And, check if any of them are our desired value: |
And, check if any of them are our desired value: |
||
< |
<syntaxhighlight lang="j"> 21=+/~0 2 11 19 90 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 0 0 1 0 |
0 0 0 1 0 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 1 0 0 0 |
0 1 0 0 0 |
||
0 0 0 0 0</ |
0 0 0 0 0</syntaxhighlight> |
||
Except, we want indices here, so let's toss the structure so we can get those: |
Except, we want indices here, so let's toss the structure so we can get those: |
||
< |
<syntaxhighlight 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 |
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 |
I.,21=+/~0 2 11 19 90 |
||
8 16</ |
8 16</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="j"> $21=+/~0 2 11 19 90 |
||
5 5 |
5 5 |
||
5 5#:I.,21=+/~0 2 11 19 90 |
5 5#:I.,21=+/~0 2 11 19 90 |
||
1 3 |
1 3 |
||
3 1</ |
3 1</syntaxhighlight> |
||
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: |
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them: |
||
< |
<syntaxhighlight lang="j"> ($ #: I.@,)21=+/~0 2 11 19 90 |
||
1 3 |
1 3 |
||
3 1</ |
3 1</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="j"> ($ <@#: I.@,)21=+/~0 2 11 19 90 |
||
┌───┬───┐ |
┌───┬───┐ |
||
│1 3│3 1│ |
│1 3│3 1│ |
||
Line 996: | Line 1,487: | ||
└───┘ |
└───┘ |
||
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90 |
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
Finally, let's start pulling our arguments out using that three verbs combining form: |
Finally, let's start pulling our arguments out using that three verbs combining form: |
||
< |
<syntaxhighlight lang="j"> ;{.a:,~($ <@#: I.@,) 21([ = +/~@])0 2 11 19 90 |
||
1 3 |
1 3 |
||
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90 |
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="j"> ;{. 21 (a:,~ ($ <@#: I.@,)@([ = +/~@]))0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
And, let's finish the job, give this a name, and test it out: |
And, let's finish the job, give this a name, and test it out: |
||
< |
<syntaxhighlight lang="j"> twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@])) |
||
21 twosum 0 2 11 19 90 |
21 twosum 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
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.) |
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.) |
||
Line 1,018: | Line 1,509: | ||
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.) |
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.) |
||
< |
<syntaxhighlight lang="j">two_sum=:dyad define |
||
sums=. +/~ y |
sums=. +/~ y |
||
matches=. x = sums |
matches=. x = sums |
||
Line 1,024: | Line 1,515: | ||
pair_inds=. ($matches) #: sum_inds |
pair_inds=. ($matches) #: sum_inds |
||
; {. a: ,~ <"1 pair_inds |
; {. a: ,~ <"1 pair_inds |
||
)</ |
)</syntaxhighlight> |
||
And, testing: |
And, testing: |
||
< |
<syntaxhighlight lang="j"> 21 two_sum 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement: |
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement: |
||
< |
<syntaxhighlight lang="j">two_sum=:dyad define |
||
sums=. +/~ y |
sums=. +/~ y |
||
matches=. x = sums |
matches=. x = sums |
||
Line 1,043: | Line 1,534: | ||
i.0 |
i.0 |
||
end. |
end. |
||
)</ |
)</syntaxhighlight> |
||
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation: |
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation: |
||
< |
<syntaxhighlight lang="j">twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))</syntaxhighlight> |
||
'''Alternative approach''' |
'''Alternative approach''' |
||
Line 1,053: | Line 1,544: | ||
An alternative method for identifying and returning non-duplicate indicies of the pairs follows. |
An alternative method for identifying and returning non-duplicate indicies of the pairs follows. |
||
< |
<syntaxhighlight lang="j"> 21 (= +/~) 0 2 11 19 90 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 0 0 1 0 |
0 0 0 1 0 |
||
0 0 0 0 0 |
0 0 0 0 0 |
||
0 1 0 0 0 |
0 1 0 0 0 |
||
0 0 0 0 0</ |
0 0 0 0 0</syntaxhighlight> |
||
The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality. |
The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality. |
||
< |
<syntaxhighlight lang="j">zeroLowerTri=: * [: </~ i.@# |
||
getIdx=: 4 $. $. |
getIdx=: 4 $. $. |
||
twosum_alt=: getIdx@zeroLowerTri@(= +/~)</ |
twosum_alt=: getIdx@zeroLowerTri@(= +/~)</syntaxhighlight> |
||
Testing ... |
Testing ... |
||
< |
<syntaxhighlight lang="j"> 21 twosum_alt 0 2 11 19 90 |
||
1 3</ |
1 3</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Lua}} |
{{trans|Lua}} |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
public class TwoSum { |
public class TwoSum { |
||
Line 1,092: | Line 1,583: | ||
return null; |
return null; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>[1, 3]</pre> |
<pre>[1, 3]</pre> |
||
Line 1,106: | Line 1,597: | ||
in the map result are eliminated by the concat. |
in the map result are eliminated by the concat. |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
var concatMap = function (f, xs) { |
var concatMap = function (f, xs) { |
||
return [].concat.apply([], xs.map(f)) |
return [].concat.apply([], xs.map(f)) |
||
Line 1,121: | Line 1,612: | ||
}(21, [0, 2, 11, 19, 90]); |
}(21, [0, 2, 11, 19, 90]); |
||
})(); |
})(); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<lang |
<syntaxhighlight lang="javascript">[[1,3]]</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
Line 1,130: | Line 1,621: | ||
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc. |
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc. |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,180: | Line 1,671: | ||
sumTwo(21, [0, 2, 11, 19, 90, 10]) |
sumTwo(21, [0, 2, 11, 19, 90, 10]) |
||
); |
); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[[1,3],[2,5]]</pre> |
<pre>[[1,3],[2,5]]</pre> |
||
Line 1,186: | Line 1,677: | ||
=={{header|Jsish}}== |
=={{header|Jsish}}== |
||
Based on Javascript entry. |
Based on Javascript entry. |
||
< |
<syntaxhighlight lang="javascript">/* Two Sum, in Jsish */ |
||
function twoSum(target, list) { |
function twoSum(target, list) { |
||
var concatMap = function (f, xs) { |
var concatMap = function (f, xs) { |
||
Line 1,207: | Line 1,698: | ||
;twoSum(21, list); |
;twoSum(21, list); |
||
;list[twoSum(21, list)[0][0]]; |
;list[twoSum(21, list)[0][0]]; |
||
;list[twoSum(21, list)[0][1]];</ |
;list[twoSum(21, list)[0][1]];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,220: | Line 1,711: | ||
'''Works with gojq, the Go implementation of jq. |
'''Works with gojq, the Go implementation of jq. |
||
{{trans|Julia}} |
{{trans|Julia}} |
||
< |
<syntaxhighlight lang="jq">def twosum($s): |
||
. as $v |
. as $v |
||
| {i: 0, j: ($v|length - 1) } |
| {i: 0, j: ($v|length - 1) } |
||
Line 1,231: | Line 1,722: | ||
[0, 2, 11, 19, 90] |
[0, 2, 11, 19, 90] |
||
| (twosum(21), twosum(25)) |
| (twosum(21), twosum(25)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,241: | Line 1,732: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">function twosum(v::Vector, s) |
||
i = 1 |
i = 1 |
||
j = length(v) |
j = length(v) |
||
Line 1,256: | Line 1,747: | ||
end |
end |
||
@show twosum([0, 2, 11, 19, 90], 21)</ |
@show twosum([0, 2, 11, 19, 90], 21)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,262: | Line 1,753: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1 |
||
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? { |
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? { |
||
Line 1,290: | Line 1,781: | ||
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum") |
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,296: | Line 1,787: | ||
The numbers with indices 1 and 3 sum to 21 |
The numbers with indices 1 and 3 sum to 21 |
||
</pre> |
</pre> |
||
=={{header|Liberty BASIC}}== |
|||
<syntaxhighlight lang="liberty basic">myArray(0) = 0 |
|||
myArray(1) = 2 |
|||
myArray(2) = 11 |
|||
myArray(3) = 19 |
|||
myArray(4) = 90 |
|||
sum = 21 |
|||
Print twoToSum$("myArray", sum, 0, 4) |
|||
End |
|||
Function twoToSum$(arrayName$, targetSum, minElement, maxElement) |
|||
i = minElement : j = maxElement |
|||
While (i < j) |
|||
Select Case |
|||
Case (Eval(arrayName$;"(";i;")") + Eval(arrayName$;"(";j;")")) < targetSum |
|||
i = (i + 1) |
|||
Case (Eval(arrayName$;"(";i;")") + Eval(arrayName$;"(";j;")")) > targetSum |
|||
j = (j - 1) |
|||
Case Else |
|||
twoToSum$ = "[";i;",";j;"]" |
|||
Exit Function |
|||
End Select |
|||
Wend |
|||
twoToSum$ = "[]" |
|||
End Function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,3]</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Lua uses one-based indexing. |
Lua uses one-based indexing. |
||
< |
<syntaxhighlight lang="lua">function twoSum (numbers, sum) |
||
local i, j, s = 1, #numbers |
local i, j, s = 1, #numbers |
||
while i < j do |
while i < j do |
||
Line 1,314: | Line 1,835: | ||
end |
end |
||
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</ |
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2,4</pre> |
<pre>2,4</pre> |
||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">two_sum := proc(arr, sum) |
||
local i,j,temp: |
local i,j,temp: |
||
i,j := 1,numelems(arr): |
i,j := 1,numelems(arr): |
||
Line 1,335: | Line 1,856: | ||
end proc: |
end proc: |
||
L := Array([0,2,2,11,19,19,90]); |
L := Array([0,2,2,11,19,19,90]); |
||
two_sum(L, 21);</ |
two_sum(L, 21);</syntaxhighlight> |
||
{{Out|Output}} |
{{Out|Output}} |
||
Note that Maple does 1 based indexing. |
Note that Maple does 1 based indexing. |
||
<pre> |
<pre> |
||
[2,5] |
[2,5] |
||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">twoSum[data_List, sum_] := |
|||
Block[{indices = Subsets[Range@Length@data, {2}]}, |
|||
Cases[indices, _?(Total@data[[#]] == sum &)]] |
|||
twoSum[{0, 2, 11, 19, 90}, 21] // TableForm</syntaxhighlight> |
|||
{{out}}<pre> |
|||
2 4 |
|||
Note, indexing in Mathematica starts at 1 |
|||
</pre> |
</pre> |
||
=={{header|MiniScript}}== |
=={{header|MiniScript}}== |
||
< |
<syntaxhighlight lang="miniscript">twoSum = function(numbers, sum) |
||
// Make a map of values to their indices in the numbers array |
// Make a map of values to their indices in the numbers array |
||
// as we go, so we will know when we've found a match. |
// as we go, so we will know when we've found a match. |
||
Line 1,354: | Line 1,886: | ||
end function |
end function |
||
print twoSum([0, 2, 11, 19, 90], 21)</ |
print twoSum([0, 2, 11, 19, 90], 21)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,360: | Line 1,892: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">MODULE TwoSum; |
||
FROM FormatString IMPORT FormatString; |
FROM FormatString IMPORT FormatString; |
||
FROM Terminal IMPORT WriteString,ReadChar; |
FROM Terminal IMPORT WriteString,ReadChar; |
||
Line 1,405: | Line 1,937: | ||
WriteString(buf); |
WriteString(buf); |
||
ReadChar; |
ReadChar; |
||
END TwoSum.</ |
END TwoSum.</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">proc twoSum(src: openarray[int], target: int): array[2, int] = |
||
if src.len < 2: |
if src.len < 2: |
||
return |
return |
||
Line 1,441: | Line 1,973: | ||
main()</ |
main()</syntaxhighlight> |
||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">class TwoSum { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
sum := 21; |
sum := 21; |
||
Line 1,487: | Line 2,019: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 1,497: | Line 2,029: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="ocaml">let get_sums ~numbers ~sum = |
||
let n = Array.length numbers in |
let n = Array.length numbers in |
||
let res = ref [] in |
let res = ref [] in |
||
Line 1,517: | Line 2,049: | ||
List.iter (fun (i, j) -> |
List.iter (fun (i, j) -> |
||
Printf.printf "# Found: %d %d\n" i j |
Printf.printf "# Found: %d %d\n" i j |
||
) res</ |
) res</syntaxhighlight> |
||
Will return all possible sums, not just the first one found. |
Will return all possible sums, not just the first one found. |
||
Line 1,528: | Line 2,060: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang="oorexx">a=.array~of( -5, 26, 0, 2, 11, 19, 90) |
||
x=21 |
x=21 |
||
n=0 |
n=0 |
||
Line 1,540: | Line 2,072: | ||
End |
End |
||
If n=0 Then |
If n=0 Then |
||
Say '[] - no items found' </ |
Say '[] - no items found' </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0,1] |
<pre>[0,1] |
||
Line 1,547: | Line 2,079: | ||
=={{header|Pascal}}== |
=={{header|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 ). |
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 ). |
||
< |
<syntaxhighlight lang="pascal">program twosum; |
||
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
||
uses |
uses |
||
Line 1,662: | Line 2,194: | ||
else |
else |
||
writeln('No solution found'); |
writeln('No solution found'); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,676: | Line 2,208: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 1,698: | Line 2,230: | ||
@indices = two_sum(25, @numbers); |
@indices = two_sum(25, @numbers); |
||
say join(', ', @indices) || 'No match';</ |
say join(', ', @indices) || 'No match';</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1, 3 |
<pre>1, 3 |
||
Line 1,704: | Line 2,236: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
Line 1,716: | Line 2,248: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #000000;">twosum</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span><span style="color: #000000;">21</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">twosum</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span><span style="color: #000000;">21</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">numbers</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">twosum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">numbers</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">numbers</span><span style="color: #0000FF;">)</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">numbers</span><span style="color: #0000FF;">)</span> |
||
Line 1,730: | Line 2,262: | ||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> |
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{Out}} |
{{Out}} |
||
Phix uses 1-based indexes |
Phix uses 1-based indexes |
||
Line 1,738: | Line 2,270: | ||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
< |
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
||
def two_sum /# arr num -- n #/ |
def two_sum /# arr num -- n #/ |
||
Line 1,759: | Line 2,291: | ||
( 0 2 11 19 90 ) |
( 0 2 11 19 90 ) |
||
21 two_sum ? |
21 two_sum ? |
||
25 two_sum ?</ |
25 two_sum ?</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[2, 19] |
<pre>[2, 19] |
||
Line 1,767: | Line 2,299: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de twosum (Lst N) |
||
(for ((I . A) Lst A (cdr A)) |
(for ((I . A) Lst A (cdr A)) |
||
(T |
(T |
||
Line 1,777: | Line 2,309: | ||
(twosum (0 2 11 19 90) 21) |
(twosum (0 2 11 19 90) 21) |
||
(twosum (-3 -2 0 1 5 8 11) 17) |
(twosum (-3 -2 0 1 5 8 11) 17) |
||
(twosum (-8 -2 -1 1 5 9 11) 0) )</ |
(twosum (-8 -2 -1 1 5 9 11) 0) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(2 . 4) NIL (3 . 4)</pre> |
<pre>(2 . 4) NIL (3 . 4)</pre> |
||
Line 1,783: | Line 2,315: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
Lazy, '''very''' lazy. |
Lazy, '''very''' lazy. |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
$numbers = @(0, 2, 11, 19, 90) |
$numbers = @(0, 2, 11, 19, 90) |
||
$sum = 21 |
$sum = 21 |
||
Line 1,809: | Line 2,341: | ||
Expression = { @($_.FirstIndex, $_.SecondIndex) } |
Expression = { @($_.FirstIndex, $_.SecondIndex) } |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,819: | Line 2,351: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="python">def two_sum(arr, num): |
||
i = 0 |
i = 0 |
||
j = len(arr) - 1 |
j = len(arr) - 1 |
||
Line 1,834: | Line 2,366: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
print(two_sum(numbers, 21)) |
print(two_sum(numbers, 21)) |
||
print(two_sum(numbers, 25))</ |
print(two_sum(numbers, 25))</syntaxhighlight> |
||
or, in terms of '''itertools.product''': |
or, in terms of '''itertools.product''': |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Finding two integers that sum to a target value.''' |
||
from itertools import (product) |
from itertools import (product) |
||
Line 1,922: | Line 2,454: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10] |
<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10] |
||
Line 1,947: | Line 2,479: | ||
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''': |
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''': |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Finding two integers that sum to a target value.''' |
||
from itertools import chain |
from itertools import chain |
||
Line 1,998: | Line 2,530: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[(1, 3), (2, 5)] |
<pre>[(1, 3), (2, 5)] |
||
Line 2,007: | Line 2,539: | ||
So… I initially misread the task as "return the two integers" and then realised it was "…the indices of…", but that's OK — it just meant writing an extra word to find the indices, given the numbers. |
So… I initially misread the task as "return the two integers" and then realised it was "…the indices of…", but that's OK — it just meant writing an extra word to find the indices, given the numbers. |
||
The last three lines of <code>task</code> are in case the two integers found by <code> |
The last three lines of <code>task</code> are in case the two integers found by <code>twosum</code> are equal - in which case, as <code>find</code> finds the first instance in the array and the array is sorted, we can safely take the index plus one as the second index. |
||
< |
<syntaxhighlight lang="quackery"> [ 0 peek ] is first ( [ --> n ) |
||
[ -1 peek ] is last ( [ --> n ) |
[ -1 peek ] is last ( [ --> n ) |
||
Line 2,041: | Line 2,573: | ||
' [ 0 2 11 19 20 ] 21 task echo cr |
' [ 0 2 11 19 20 ] 21 task echo cr |
||
' [ 0 2 11 19 20 ] 25 task echo cr |
' [ 0 2 11 19 20 ] 25 task echo cr |
||
' [ 0 2 12 12 20 ] 24 task echo cr</ |
' [ 0 2 12 12 20 ] 24 task echo cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,049: | Line 2,581: | ||
[ 2 3 ] |
[ 2 3 ] |
||
</pre> |
</pre> |
||
=={{header|R}}== |
|||
<syntaxhighlight lang="R"> |
|||
numbers<- c(0,2,11,19,28,90) |
|||
two_sum<- function(numbers,s){ |
|||
all_sums <- outer(numbers,numbers,"+")==s |
|||
all_sums[lower.tri(all_sums)] <- NA |
|||
which(all_sums,arr.ind = T) #first index is in the "row" column, and second index is in the "col" column |
|||
} |
|||
#In R, index begins from 0 |
|||
print(two_sum(numbers,21)) #should return 2 4 |
|||
cat("\n") |
|||
print(two_sum(numbers,24)) #should return nothing |
|||
cat("\n") |
|||
print(two_sum(numbers,30)) #should return 3 4 and 2 5 |
|||
</syntaxhighlight> |
|||
'''Output''' |
|||
<pre> |
|||
row col |
|||
[1,] 2 4 |
|||
row col |
|||
row col |
|||
[1,] 3 4 |
|||
[2,] 2 5 |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(define (two-sum v m) |
(define (two-sum v m) |
||
(let inr ((l 0) (r (sub1 (vector-length v)))) |
(let inr ((l 0) (r (sub1 (vector-length v)))) |
||
Line 2,066: | Line 2,628: | ||
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6)) |
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6)) |
||
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f) |
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f) |
||
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))</ |
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))</syntaxhighlight> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 2,073: | Line 2,635: | ||
===Procedural=== |
===Procedural=== |
||
{{trans|zkl}} |
{{trans|zkl}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub two_sum ( @numbers, $sum ) { |
||
die '@numbers is not sorted' unless [<=] @numbers; |
die '@numbers is not sorted' unless [<=] @numbers; |
||
Line 2,088: | Line 2,650: | ||
say two_sum ( 0, 2, 11, 19, 90 ), 21; |
say two_sum ( 0, 2, 11, 19, 90 ), 21; |
||
say two_sum ( 0, 2, 11, 19, 90 ), 25;</ |
say two_sum ( 0, 2, 11, 19, 90 ), 25;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(1 3) |
<pre>(1 3) |
||
Line 2,096: | Line 2,658: | ||
The two versions differ only in how one 'reads' the notional flow of processing: left-to-right versus right-to-left. |
The two versions differ only in how one 'reads' the notional flow of processing: left-to-right versus right-to-left. |
||
Both return all pairs that sum to the target value, not just the first (e.g. for input of <code>0 2 10 11 19 90</code> would get indices 1/4 and 2/3). |
Both return all pairs that sum to the target value, not just the first (e.g. for input of <code>0 2 10 11 19 90</code> would get indices 1/4 and 2/3). |
||
<lang |
<syntaxhighlight lang="raku" line>sub two-sum-lr (@a, $sum) { |
||
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique |
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique |
||
( |
( |
||
Line 2,121: | Line 2,683: | ||
say two-sum-rl(@a, $_); |
say two-sum-rl(@a, $_); |
||
say two-sum-lr(@a, $_); |
say two-sum-lr(@a, $_); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(1 3) |
<pre>(1 3) |
||
Line 2,130: | Line 2,692: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX */ |
||
list='-5 26 0 2 11 19 90' |
list='-5 26 0 2 11 19 90' |
||
Do i=0 By 1 Until list='' |
Do i=0 By 1 Until list='' |
||
Line 2,150: | Line 2,712: | ||
Say '[] - no items found' |
Say '[] - no items found' |
||
Else |
Else |
||
Say z 'solutions found'</ |
Say z 'solutions found'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0,1] -5 26 21 |
<pre>[0,1] -5 26 21 |
||
Line 2,170: | Line 2,732: | ||
A little extra code was added to have the output columns aligned. |
A little extra code was added to have the output columns aligned. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds two numbers in a list of numbers that sum to a particular target.*/ |
||
numeric digits 500 /*be able to handle some larger numbers*/ |
numeric digits 500 /*be able to handle some larger numbers*/ |
||
parse arg targ list /*obtain optional arguments from the CL*/ |
parse arg targ list /*obtain optional arguments from the CL*/ |
||
Line 2,193: | Line 2,755: | ||
say |
say |
||
if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/ |
if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/ |
||
say 'number of solutions found: ' sol /*stick a fork in it, we're all done. */</ |
say 'number of solutions found: ' sol /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 2,239: | Line 2,801: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Two Sum |
# Project : Two Sum |
||
Line 2,259: | Line 2,821: | ||
next |
next |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,265: | Line 2,827: | ||
target sum: 21 |
target sum: 21 |
||
a solution: [1 3] |
a solution: [1 3] |
||
</pre> |
|||
=={{header|RPL}}== |
|||
≪ → array sum |
|||
≪ { } |
|||
1 array SIZE '''FOR''' j |
|||
array j 0 PUT |
|||
sum array j GET - |
|||
'''IF''' POS '''THEN''' |
|||
j LAST |
|||
'''IF''' DUP2 > '''THEN''' SWAP '''END''' |
|||
R→C |
|||
'''IF''' DUP2 POS '''THEN''' DROP '''ELSE''' + '''END''' |
|||
'''END NEXT''' |
|||
≫ ≫ ‘<span style="color:blue">TWOSUM</span>’ STO |
|||
{0 2 11 19 90} 21 <span style="color:blue">TWOSUM</span> |
|||
{0 2 11 19 90} 22 <span style="color:blue">TWOSUM</span> |
|||
{0 2 3 3 4 11 17 17 18 19 90} 21 <span style="color:blue">TWOSUM</span> |
|||
{{out}} |
|||
<pre> |
|||
3: { (2,4) } |
|||
2: { } |
|||
1: { (2,10) (3,9) (4,9) (5,7) (5,8) } |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def two_sum(numbers, sum) |
||
numbers.each_with_index do |x,i| |
numbers.each_with_index do |x,i| |
||
if j = numbers.index(sum - x) then return [i,j] end |
if j = numbers.index(sum - x) then return [i,j] end |
||
Line 2,277: | Line 2,863: | ||
numbers = [0, 2, 11, 19, 90] |
numbers = [0, 2, 11, 19, 90] |
||
p two_sum(numbers, 21) |
p two_sum(numbers, 21) |
||
p two_sum(numbers, 25)</ |
p two_sum(numbers, 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,286: | Line 2,872: | ||
When the size of the Array is bigger, the following is more suitable. |
When the size of the Array is bigger, the following is more suitable. |
||
< |
<syntaxhighlight lang="ruby">def two_sum(numbers, sum) |
||
numbers.each_with_index do |x,i| |
numbers.each_with_index do |x,i| |
||
key = sum - x |
key = sum - x |
||
Line 2,294: | Line 2,880: | ||
end |
end |
||
[] |
[] |
||
end</ |
end</syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">use std::cmp::Ordering; |
||
use std::ops::Add; |
use std::ops::Add; |
||
Line 2,327: | Line 2,913: | ||
println!("{:?}", two_sum(&arr, sum)); |
println!("{:?}", two_sum(&arr, sum)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,335: | Line 2,921: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">import java.util |
||
object TwoSum extends App { |
object TwoSum extends App { |
||
Line 2,351: | Line 2,937: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/GxVfCE7/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/S5aks2gRTcqcy1VUWJ6GzQ Scastie (JVM)]. |
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/GxVfCE7/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/S5aks2gRTcqcy1VUWJ6GzQ Scastie (JVM)]. |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">func two_sum(numbers, sum) { |
||
var (i, j) = (0, numbers.end) |
var (i, j) = (0, numbers.end) |
||
while (i < j) { |
while (i < j) { |
||
Line 2,369: | Line 2,955: | ||
say two_sum([0, 2, 11, 19, 90], 21) |
say two_sum([0, 2, 11, 19, 90], 21) |
||
say two_sum([0, 2, 11, 19, 90], 25)</ |
say two_sum([0, 2, 11, 19, 90], 25)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,378: | Line 2,964: | ||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
Notice that array indexes start at 1 in Stata. |
Notice that array indexes start at 1 in Stata. |
||
< |
<syntaxhighlight lang="stata">function find(a, x) { |
||
i = 1 |
i = 1 |
||
j = length(a) |
j = length(a) |
||
Line 2,393: | Line 2,979: | ||
+---------+ |
+---------+ |
||
1 | 2 4 | |
1 | 2 4 | |
||
+---------+</ |
+---------+</syntaxhighlight> |
||
=={{header|Uiua}}== |
|||
Works by using ⊞f. to form a cross product (similar to APL's ∘.f⍨). |
|||
The resulting additions are multiplied with a mask of the upper right half (⊞>.⇡⧻) to remove extraneous answers. |
|||
<syntaxhighlight lang="uiua">f ← ⊚=×⊞>.⇡⧻.⊞+. |
|||
f 0_2_11_19_90 21</syntaxhighlight> |
|||
{{out}} |
|||
<pre>╭─ |
|||
╷ 1 3 |
|||
╯</pre> |
|||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
< |
<syntaxhighlight lang="vala">void main() { |
||
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0; |
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0; |
||
Line 2,410: | Line 3,006: | ||
if (check == 0) |
if (check == 0) |
||
print("[]"); |
print("[]"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1,3]</pre> |
<pre>[1,3]</pre> |
||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">Option Explicit |
||
Function two_sum(a As Variant, t As Integer) As Variant |
Function two_sum(a As Variant, t As Integer) As Variant |
||
Dim i, j As Integer |
Dim i, j As Integer |
||
Line 2,442: | Line 3,038: | ||
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17)) |
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17)) |
||
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0)) |
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0)) |
||
End Sub</ |
End Sub</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,454: | Line 3,050: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Function TwoSum(numbers As Integer(), sum As Integer) As Integer() |
Function TwoSum(numbers As Integer(), sum As Integer) As Integer() |
||
Line 2,478: | Line 3,074: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1, 3</pre> |
<pre>1, 3</pre> |
||
=={{header|V (Vlang)}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="v (vlang)"> |
|||
fn two_sum(a []int, target_sum int) (int, int, bool) { |
|||
len := a.len |
|||
if len < 2 {return 0, 0, false} |
|||
for i in 0..len - 1 { |
|||
if a[i] <= target_sum { |
|||
for j in i + 1..len { |
|||
sum := a[i] + a[j] |
|||
if sum == target_sum {return i, j, true} |
|||
if sum > target_sum {break} |
|||
} |
|||
} |
|||
else {break} |
|||
} |
|||
return 0, 0, false |
|||
} |
|||
fn main() { |
|||
a := [0, 2, 11, 19, 90] |
|||
target_sum := 21 |
|||
p1, p2, ok := two_sum(a, target_sum) |
|||
if !ok {println("No two numbers were found whose sum is $target_sum")} |
|||
else {println("The numbers with indices $p1 and $p2 sum to $target_sum")} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The numbers with indices 1 and 3 sum to 21 |
|||
</pre> |
|||
=={{header|X86 Assembly}}== |
=={{header|X86 Assembly}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
{{works with|nasm}} |
{{works with|nasm}} |
||
< |
<syntaxhighlight lang="asm"> |
||
section .data |
section .data |
||
outputArr dd 0,0,0 |
outputArr dd 0,0,0 |
||
Line 2,527: | Line 3,156: | ||
mov eax, outputArr ;address of outputArr is returned in eax |
mov eax, outputArr ;address of outputArr is returned in eax |
||
ret |
ret |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
< |
<syntaxhighlight lang="wren">var twosum = Fn.new { |a, n| |
||
var c = a.count |
var c = a.count |
||
if (c < 2) return [] |
if (c < 2) return [] |
||
Line 2,553: | Line 3,182: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,564: | Line 3,193: | ||
Indices: [0, 4] sum to 90 (0 + 90 = 90) |
Indices: [0, 4] sum to 90 (0 + 90 = 90) |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
Test cases from Algol 68. |
|||
<syntaxhighlight lang="xpl0">proc TwoSum(Size, Array, Sum); |
|||
int Size, Array, Sum, I, J; |
|||
[Text(0, "["); |
|||
for I:= 0 to Size-1 do |
|||
for J:= I+1 to Size-1 do |
|||
if Array(I) + Array(J) = Sum then |
|||
[IntOut(0, I); Text(0, ", "); IntOut(0, J); |
|||
J:= Size; I:= Size; |
|||
]; |
|||
Text(0, "]^m^j"); |
|||
]; |
|||
[TwoSum(5, [ 0, 2, 11, 19, 90], 21); \ should be [1, 3] |
|||
TwoSum(7, [-8, -2, 0, 1, 5, 8, 11], 3); \ should be [0, 6] (or [1, 4]) |
|||
TwoSum(7, [-3, -2, 0, 1, 5, 8, 11], 17); \ should be [] |
|||
TwoSum(7, [-8, -2, -1, 1, 5, 9, 11], 0); \ should be [2, 3] |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 3] |
|||
[0, 6] |
|||
[] |
|||
[2, 3] |
|||
</pre> |
|||
=={{header|Yabasic}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Two_sum |
|||
// by Galileo, 04/2022 |
|||
Sub twoSum (a(), b(), targetSum) |
|||
local ub, sum, i, j |
|||
ub = arraysize(a(), 1) |
|||
For i = 1 To ub - 1 |
|||
If a(i) <= targetSum Then |
|||
For j = i + 1 To ub |
|||
sum = a(i) + a(j) |
|||
If sum = targetSum Then |
|||
Redim b(2) |
|||
b(1) = i : b(2) = j |
|||
Return |
|||
ElsIf sum > targetSum Then |
|||
break |
|||
EndIf |
|||
Next j |
|||
Else |
|||
break |
|||
EndIf |
|||
Next i |
|||
End Sub |
|||
Dim a(5) |
|||
Dim b(1) |
|||
data 0, 2, 11, 19, 90 |
|||
for n = 1 to 5 : read a(n) : next |
|||
targetSum = 21 |
|||
twoSum(a(), b(), targetSum) |
|||
If arraysize(b(), 1) = 1 Then |
|||
Print "No two numbers were found whose sum is ", targetSum |
|||
Else |
|||
Print "The numbers with indices ", b(1), " and ", b(2), " sum to ", targetSum |
|||
End If</syntaxhighlight> |
|||
{{out}} |
|||
<pre>The numbers with indices 2 and 4 sum to 21 |
|||
---Program done, press RETURN---</pre> |
|||
=={{header|Zig}}== |
|||
'''Works with:''' 0.11.x, 0.12.0-dev.1389+42d4d07ef |
|||
<syntaxhighlight lang="zig">pub fn sumsUpTo(comptime T: type, input: []const T, target_sum: T) ?struct { usize, usize } { |
|||
if (input.len <= 1) return null; |
|||
return result: for (input[0 .. input.len - 1], 0..) |left, left_i| { |
|||
if (left > target_sum) break :result null; |
|||
const offset = left_i + 1; |
|||
for (input[offset..], offset..) |right, right_i| { |
|||
const current_sum = left + right; |
|||
if (current_sum < target_sum) continue; |
|||
if (current_sum == target_sum) break :result .{ left_i, right_i }; |
|||
if (current_sum > target_sum) break; |
|||
} |
|||
} else null; |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zig">const std = @import("std"); |
|||
pub fn main() std.fs.File.WriteError!void { |
|||
const stdout = std.io.getStdOut(); |
|||
const stdout_w = stdout.writer(); |
|||
const stderr = std.io.getStdErr(); |
|||
const stderr_w = stderr.writer(); |
|||
const a = [_]u32{ 0, 2, 11, 19, 90 }; |
|||
const target_sum: u32 = 21; |
|||
const optional_indexes = sumsUpTo(u32, &a, target_sum); |
|||
if (optional_indexes) |indexes| { |
|||
try stdout_w.print("Result: [{d}, {d}].\n", .{ indexes[0], indexes[1] }); |
|||
} else { |
|||
try stderr_w.print("Numbers with sum {d} were not found!\n", .{target_sum}); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Result: [1, 3]. |
|||
</pre> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
The sorted O(n) no external storage solution: |
The sorted O(n) no external storage solution: |
||
< |
<syntaxhighlight lang="zkl">fcn twoSum(sum,ns){ |
||
i,j:=0,ns.len()-1; |
i,j:=0,ns.len()-1; |
||
while(i<j){ |
while(i<j){ |
||
Line 2,575: | Line 3,319: | ||
else if(s>sum) j-=1; |
else if(s>sum) j-=1; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">twoSum2(21,T(0,2,11,19,90)).println(); |
||
twoSum2(25,T(0,2,11,19,90)).println();</ |
twoSum2(25,T(0,2,11,19,90)).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,584: | Line 3,328: | ||
</pre> |
</pre> |
||
The unsorted O(n!) all solutions solution: |
The unsorted O(n!) all solutions solution: |
||
< |
<syntaxhighlight lang="zkl">fcn twoSum2(sum,ns){ |
||
Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum }) // lazy combos |
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)) }) |
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) }) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">twoSum2(21,T(0,2,11,19,90,21)).println(); |
||
twoSum2(25,T(0,2,11,19,90,21)).println();</ |
twoSum2(25,T(0,2,11,19,90,21)).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 11:56, 6 July 2024
- Task
Given a sorted array of integers (with possibly duplicates), 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. The solution is not necessarily unique.
- 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
11l
F two_sum(arr, num)
V i = 0
V j = arr.len - 1
L i < j
I arr[i] + arr[j] == num
R [i, j]
I arr[i] + arr[j] < num
i++
E
j--
R [Int]()
V numbers = [0, 2, 11, 19, 90]
print(two_sum(numbers, 21))
print(two_sum(numbers, 25))
- Output:
[1, 3] []
AArch64 Assembly
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program twosum64.s */
/************************************/
/* Constantes */
/************************************/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result : ["
szMessResult1: .asciz ","
szMessResult2: .asciz "]\n"
szMessStart: .asciz "Program 64 bits start.\n"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "No soluce ! \n"
tabArray: .quad 0, 2, 11, 19, 90
.equ TABARRAYSIZE, (. - tabArray) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrszMessStart
bl affichageMess
ldr x0,qAdrtabArray
mov x1,#21
bl rechTwoNumbers
cmp x0,#-1 // no soluce
beq 100f
mov x2,x1
ldr x1,qAdrsZoneConv
bl conversion10 // decimal conversion
strb wzr,[x1,x0]
mov x0,x2
ldr x1,qAdrsZoneConv1
bl conversion10 // decimal conversion
strb wzr,[x1,x0]
mov x0,#5 // number string to display
ldr x1,qAdrszMessResult
ldr x2,qAdrsZoneConv // insert conversion in message
ldr x3,qAdrszMessResult1
ldr x4,qAdrsZoneConv1
ldr x5,qAdrszMessResult2
stp x5,x4,[sp,-16]! // save registers
bl displayStrings // display message
add sp,sp,#16
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsZoneConv: .quad sZoneConv
qAdrsZoneConv1: .quad sZoneConv1
qAdrszMessResult: .quad szMessResult
qAdrszMessResult1: .quad szMessResult1
qAdrszMessResult2: .quad szMessResult2
qAdrszMessErreur: .quad szMessErreur
qAdrszMessStart: .quad szMessStart
qAdrtabArray: .quad tabArray
/******************************************************************/
/* search two numbers to sum */
/******************************************************************/
/* x0 array addressr */
/* x1 sum */
/* x0 return first index */
/* x1 return second index */
rechTwoNumbers:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
stp x5,x6,[sp,-16]! // save registers
stp x7,x8,[sp,-16]! // save registers
mov x3,#0 // init result
1: // loop
ldr x4,[x0,x3,lsl #3] // load first number
mov x5,x3 // indice2
2:
ldr x6,[x0,x5,lsl #3] // load 2th number
add x7,x6,x4 // add the two numbers
cmp x7,x1 // equal to origin
beq 3f // yes -> ok
add x5,x5,#1 // increment indice2
cmp x5,#TABARRAYSIZE // end ?
blt 2b // no -> loop
add x3,x3,#1 // increment indice1
cmp x3,#TABARRAYSIZE - 1 // end ?
blt 1b // no loop
// not found
ldr x0,qAdrszMessErreur
bl affichageMess
mov x0,#-1
mov x1,#-1
b 100f // end
3:
mov x0,x3 // return results
mov x1,x5
100:
ldp x7,x8,[sp],16 // restaur registers
ldp x5,x6,[sp],16 // restaur registers
ldp x3,x4,[sp],16 // restaur registers
ldp x2,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* display multi strings */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: // INFO: displayStrings
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
add fp,sp,#48 // save paraméters address (6 registers saved * 8 bytes)
mov x4,x0 // save strings number
cmp x4,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x4,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x4,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x4,#3
ble 100f
mov x3,#3
sub x2,x4,#4
1: // loop extract address string on stack
ldr x0,[fp,x2,lsl #3]
bl affichageMess
subs x2,x2,#1
bge 1b
100:
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../includeARM64.inc"
- Output:
Program 64 bits start. Result : [1,3]
Action!
PROC PrintArray(INT ARRAY a INT len)
INT i
Put('[)
FOR i=0 TO len-1
DO
PrintI(a(i))
IF i<len-1 THEN
Put(' )
FI
OD
Put(']) PutE()
RETURN
PROC PrintPairs(INT ARRAY a INT len,sum)
INT i,j,p1,p2,s,count
count=0
FOR i=0 TO len-2
DO
p1=a(i)
FOR j=i+1 TO len-1
DO
p2=a(j)
s=p1+p2
IF s=sum THEN
PrintF("(%I,%I) ",i,j)
count==+1
ELSEIF s>sum THEN
EXIT
FI
OD
OD
IF count=0 THEN
Print("none")
FI
PutE()
RETURN
PROC Test(INT ARRAY a INT len,sum)
Print("Array: ") PrintArray(a,len)
Print("Sum: ") PrintIE(sum)
Print("Pairs: ") PrintPairs(a,len,sum)
PutE()
RETURN
PROC Main()
INT ARRAY a=[0 2 11 19 90]
INT ARRAY b=[0 2 3 3 4 11 17 17 18 19 90]
Test(a,5,21)
Test(a,5,22)
Test(b,11,21)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Array: [0 2 11 19 90] Sum: 21 Pairs: (1,3) Array: [0 2 11 19 90] Sum: 22 Pairs: none Array: [0 2 3 3 4 11 17 17 18 19 90] Sum: 21 Pairs: (1,9) (2,8) (3,8) (4,6) (4,7)
Aime
integer i, u, v;
index x;
list l;
l_bill(l, 0, 0, 2, 11, 19, 90);
for (i, u in l) {
x[u] = i;
if (i_jack(v, x, 21 - u)) {
o_(v, " ", i, "\n");
break;
}
}
- Output:
1 3
ALGOL 68
# returns the subscripts of a pair of numbers in a that sum to sum, a is assumed to be sorted #
# if there isn't a pair of numbers that summs to sum, an empty array is returned #
PRIO TWOSUM = 9;
OP TWOSUM = ( []INT a, INT sum )[]INT:
BEGIN
BOOL found := FALSE;
INT i := LWB a;
INT j := UPB a;
WHILE i < j AND NOT found DO
INT s = a[ i ] + a[ j ];
IF s = sum THEN
found := TRUE
ELIF s < sum THEN
i +:= 1
ELSE
j -:= 1
FI
OD;
IF found THEN ( i, j ) ELSE () FI
END # TWOSUM # ;
# test the TWOSUM operator #
PROC print twosum = ( []INT a, INT sum )VOID:
BEGIN
[]INT pair = a[ AT 0 ] TWOSUM sum;
IF LWB pair > UPB pair THEN
# no pair with the required sum #
print( ( "[]", newline ) )
ELSE
# have a pair #
print( ( "[", whole( pair[ LWB pair ], 0 ), ", ", whole( pair[ UPB pair ], 0 ), "]", newline ) )
FI
END # print twosum # ;
print twosum( ( 0, 2, 11, 19, 90 ), 21 ); # should be [1, 3] #
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) #
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] #
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #
- Output:
[1, 3] [0, 6] [] [2, 3]
APL
Works with Dyalog APL.
∘.+⍨ ⍺ makes a table that is the outer sum of the left argument (the numbers).
We want to remove the diagonal, to avoid edge cases. We can achieve this by setting all these numbers to an arbitrary decimal value, since two integers can't sum to a decimal.
≢⍺ is the length of the numbers. ⍳≢⍺ creates an array from 0 to the length of the numbers. ∘.=⍳≢⍺ returns an identity matrix of size ≢⍺ (using the outer product with the equality function). ⍸ returns the indices of these numbers. 0.1@ sets that list to 0.1.
Then, we just need to find where the right argument (the target) is equal to the matrix, get the indices, and return the first one (⊃).
⎕io ← 0 ⍝ sets index origin to 0
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺}
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3
- Output:
1 3
AppleScript
Functional
Nesting concatMap or (>>=) (flip concatMap) yields the cartesian product of the list with itself. Skipping products where the y index is lower than the x index (see the use of 'drop' below) ignores the 'lower triangle' of the cartesian grid, excluding mirror-image and duplicate number pairs.
Note that this draft assumes that the task and target output are specified in terms of the prevailing convention of zero-based indices.
AppleScript, unusually, happens to make internal use of one-based indices, rigid adherence to which would, of course, in this case, simply produce the wrong result :-)
-------------------------- TWO SUM -------------------------
-- twoSum :: Int -> [Int] -> [(Int, Int)]
on twoSum(n, xs)
set ixs to zip(enumFromTo(0, |length|(xs) - 1), xs)
script ijIndices
on |λ|(ix)
set {i, x} to ix
script jIndices
on |λ|(jy)
set {j, y} to jy
if (x + y) = n then
{{i, j}}
else
{}
end if
end |λ|
end script
|>>=|(drop(i + 1, ixs), jIndices)
end |λ|
end script
|>>=|(ixs, ijIndices)
end twoSum
---------------------------- TEST --------------------------
on run
twoSum(21, [0, 2, 11, 19, 90])
--> {{1, 3}} Single solution.
end run
--------------------- GENERIC FUNCTIONS --------------------
-- (>>=) :: Monad m => m a -> (a -> m b) -> m b
on |>>=|(xs, f)
concat(map(f, xs))
end |>>=|
-- concat :: [[a]] -> [a] | [String] -> String
on concat(xs)
script append
on |λ|(a, b)
a & b
end |λ|
end script
if length of xs > 0 and class of (item 1 of xs) is string then
set empty to ""
else
set empty to {}
end if
foldl(append, empty, xs)
end concat
-- drop :: Int -> a -> a
on drop(n, a)
if n < length of a then
if class of a is text then
text (n + 1) thru -1 of a
else
items (n + 1) thru -1 of a
end if
else
{}
end if
end drop
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m > n then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- length :: [a] -> Int
on |length|(xs)
length of xs
end |length|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
set lng to min(length of xs, length of ys)
set lst to {}
repeat with i from 1 to lng
set end of lst to {item i of xs, item i of ys}
end repeat
return lst
end zip
- Output:
{{1, 3}}
Idiomatic
Like the "Functional" script above, this returns multiple solutions when they're found. However it assumes a sorted list, as per the clarified task description, which allows some optimisation of the search. Also, the indices returned are 1-based, which is the AppleScript norm.
on twoSum(givenNumbers, givenSum)
script o
property lst : givenNumbers
property output : {}
end script
set listLength to (count o's lst)
repeat with i from 1 to (listLength - 1)
set n1 to item i of o's lst
repeat with j from (i + 1) to listLength
set thisSum to n1 + (item j of o's lst)
if (thisSum = givenSum) then
set end of o's output to {i, j}
else if (thisSum > givenSum) then
exit repeat
end if
end repeat
end repeat
return o's output
end twoSum
-- Test code:
twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list.
twoSum({0, 3, 11, 19, 90}, 21) -- No matches.
twoSum({-44, 0, 0, 2, 10, 11, 19, 21, 21, 21, 65, 90}, 21) -- Multiple solutions.
- Output:
{{2, 4}}
{}
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}
ARM Assembly
/* ARM assembly Raspberry PI */
/* program twosum.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result : ["
szMessResult1: .asciz ","
szMessResult2: .asciz "]\n"
szMessStart: .asciz "Program 32 bits start.\n"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "No soluce ! \n"
tabArray: .int 0, 2, 11, 19, 90
.equ TABARRAYSIZE, (. - tabArray) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrszMessStart
bl affichageMess
ldr r0,iAdrtabArray
mov r1,#21
bl rechTwoNumbers
cmp r0,#-1 @ no soluce
beq 100f
mov r2,r1
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
mov r3,#0
strb r3,[r1,r0]
mov r0,r2
ldr r1,iAdrsZoneConv1
bl conversion10 @ decimal conversion
mov r3,#0
strb r3,[r1,r0]
mov r0,#5 @ number string to display
ldr r1,iAdrszMessResult
ldr r2,iAdrsZoneConv @ insert conversion in message
ldr r3,iAdrszMessResult1
ldr r4,iAdrsZoneConv1
push {r4}
ldr r4,iAdrszMessResult2
push {r4}
bl displayStrings @ display message
add sp,#8
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsZoneConv: .int sZoneConv
iAdrsZoneConv1: .int sZoneConv1
iAdrszMessResult: .int szMessResult
iAdrszMessResult1: .int szMessResult1
iAdrszMessResult2: .int szMessResult2
iAdrszMessErreur: .int szMessErreur
iAdrszMessStart: .int szMessStart
iAdrtabArray: .int tabArray
/******************************************************************/
/* search two numbers from sum */
/******************************************************************/
/* r0 array addressr */
/* r1 sum */
/* r0 return fist index */
/* r1 return second index */
rechTwoNumbers:
push {r2-r7,lr} @ save registers
mov r3,#0 @ init result
1: @ loop
ldr r4,[r0,r3,lsl #2] @ load first number
mov r5,r3 @ indice2
2:
ldr r6,[r0,r5,lsl #2] @ load 2th number
add r7,r6,r4 @ add the two numbers
cmp r7,r1 @ equal to origin
beq 3f @ yes -> ok
add r5,r5,#1 @ increment indice2
cmp r5,#TABARRAYSIZE @ end ?
blt 2b @ no -> loop
add r3,r3,#1 @ increment indice1
cmp r3,#TABARRAYSIZE - 1 @ end ?
blt 1b @ no loop
@ not found
ldr r0,iAdrszMessErreur
bl affichageMess
mov r0,#-1
mov r1,#-1
b 100f @ end
3:
mov r0,r3 @ return results
mov r1,r5
100:
pop {r2-r7,pc}
/***************************************************/
/* display multi strings */
/***************************************************/
/* r0 contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: @ INFO: displayStrings
push {r1-r4,fp,lr} @ save des registres
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes)
mov r4,r0 @ save strings number
cmp r4,#0 @ 0 string -> end
ble 100f
mov r0,r1 @ string 1
bl affichageMess
cmp r4,#1 @ number > 1
ble 100f
mov r0,r2
bl affichageMess
cmp r4,#2
ble 100f
mov r0,r3
bl affichageMess
cmp r4,#3
ble 100f
mov r3,#3
sub r2,r4,#4
1: @ loop extract address string on stack
ldr r0,[fp,r2,lsl #2]
bl affichageMess
subs r2,#1
bge 1b
100:
pop {r1-r4,fp,pc}
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
- Output:
Program 32 bits start. Result : [1,3]
Arturo
twoSum: function [numbers, s][
loop.with:'i numbers 'x [
if not? null? j: <= index numbers s-x ->
return @[i j]
]
return []
]
nums: [0 2 11 19 90]
print ["twoSum 21:" twoSum nums 21]
print ["twoSum 25:" twoSum nums 25]
- Output:
twoSum 21: [1 3] twoSum 25: []
AutoHotkey
TwoSum(a, target){
i := 1, j := a.MaxIndex()
while(i < j){
if (a[i] + a[j] = target)
return i ", " j
else if (a[i] + a[j] < target)
i++
else if (a[i] + a[j] > target)
j--
}
return "not found"
}
Examples:
MsgBox % TwoSum([0, 2, 11, 19, 90], 21) ; returns 2, 4 (first index is 1 not 0)
Outputs:
2,4
AWK
# syntax: GAWK -f TWO_SUM.AWK
BEGIN {
numbers = "0,2,11,19,90"
print(two_sum(numbers,21))
print(two_sum(numbers,25))
exit(0)
}
function two_sum(numbers,sum, arr,i,j,s) {
i = 1
j = split(numbers,arr,",")
while (i < j) {
s = arr[i] + arr[j]
if (s == sum) {
return(sprintf("[%d,%d]",i,j))
}
else if (s < sum) {
i++
}
else {
j--
}
}
return("[]")
}
- Output:
[2,4] []
Befunge
>000pv
>&:0\`#v_00g:1+00p6p
v >$&50p110p020p
v>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+50g-!#v_48*10g8p10g1+:00g1-`v >
v >10g20g..@ v_v
"""""""""""""""""""""""""""""""""""""""""""""""v ">"p4\"v"p02:+1p4\">":g02$< :
> 20g8p20g1+:00g1-`#v_0 ^1
""""""""""""""""""""""""""""""""""""""""""""""" " 0
>^ l p
i "
a ^
F "
" \
>:#,_@ 8
p
> ^
There are a couple of caveats due to limitations of the language. The target cannot be above 127, there can be no more than 47 elements in the list and the list must be delimited by a negative number before the target value as follows:
0 2 11 19 90 -1 21
- Output:
1 3
C
#include<stdio.h>
int main()
{
int arr[5] = {0, 2, 11, 19, 90},sum = 21,i,j,check = 0;
for(i=0;i<4;i++){
for(j=i+1;j<5;j++){
if(arr[i]+arr[j]==sum){
printf("[%d,%d]",i,j);
check = 1;
break;
}
}
}
if(check==0)
printf("[]");
return 0;
}
Output :
[1,3]
C#
using System;
using System.Collections.Generic;
public class Program
{
public static void Main(string[] args)
{
int[] arr = { 0, 2, 11, 19, 90 };
const int sum = 21;
var ts = TwoSum(arr, sum);
Console.WriteLine(ts != null ? $"{ts[0]}, {ts[1]}" : "no result");
Console.ReadLine();
}
public static int[] TwoSum(int[] numbers, int sum)
{
var map = new Dictionary<int, int>();
for (int i = 0; i < numbers.Length; i++)
{
// see if the complement is stored
var key = sum - numbers[i];
if (map.ContainsKey(key))
{
return new[] { map[key], i };
}
map.Add(numbers[i], i);
}
return null;
}
}
- Output:
1, 3
C++
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
using namespace std;
pair<int, int> twoSum(vector<int> numbers, int sum) {
auto m = map<int, int>();
for (size_t i = 0; i < numbers.size(); ++i) {
// see if the complement is stored
auto key = sum - numbers[i];
if (m.find(key) != m.end()) {
return make_pair(m[key], i);
}
m[numbers[i]] = i;
}
return make_pair(-1, -1);
}
int main() {
auto numbers = vector<int>{ 0, 2, 11, 19, 90 };
const int sum = 21;
auto ts = twoSum(numbers, sum);
if (ts.first != -1) {
cout << "{" << ts.first << ", " << ts.second << "}" << endl;
} else {
cout << "no result" << endl;
}
return 0;
}
- Output:
{1,3}
D
import std.stdio;
void main() {
const arr = [0, 2, 11, 19, 90];
const sum = 21;
writeln(arr.twoSum(21));
}
/**
* Searches arr for two indexes whose value adds to sum, and returns those indexes.
* Returns an empty array if no such indexes exist.
* The values of arr are assumed to be sorted.
*/
int[] twoSum(const int[] arr, const int sum) in {
import std.algorithm.sorting : isSorted;
assert(arr.isSorted);
} out(result) {
assert(result.length == 0 || arr[result[0]] + arr[result[1]] == sum);
} body {
int i=0;
int j=arr.length-1;
while (i <= j) {
auto temp = arr[i] + arr[j];
if (temp == sum) {
return [i, j];
}
if (temp < sum) {
i++;
} else {
j--;
}
}
return [];
}
- Output:
[1, 3]
Dart
main() {
var a = [1,2,3,4,5];
var s=25,c=0;
var z=(a.length*(a.length-1))/2;
for (var x = 0; x < a.length; x++) {
print(a[x]);
}
for (var x = 0; x < a.length; x++) {
for(var y=x+1;y< a.length; y++)
{
if(a[x]+a[y]==s)
{
print([a[x],a[y]]);
break;
}
else
{
c++;
}
}
}
if(c==z)
{
print("such pair doesn't exist");
}
}
Delphi
program Two_Sum;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
System.Generics.Collections;
function TwoSum(arr: TArray<Integer>; num: Integer; var i, j: integer): boolean;
begin
TArray.Sort<Integer>(arr);
i := 0;
j := Length(arr) - 1;
while i < j do
begin
if arr[i] + arr[j] = num then
exit(True);
if arr[i] + arr[j] < num then
inc(i)
else
Dec(j);
end;
Result := false;
end;
var
i, j: Integer;
begin
if TwoSum([0, 2, 11, 19, 90], 21, i, j) then
Writeln('(', i, ',', j, ')');
if TwoSum([0, 2, 11, 19, 90], 25, i, j) then
Writeln('(', i, ',', j, ')');
Readln;
end.
- Output:
(1,3)
EasyLang
EasyLang arrays are one-based, so the indices returned are also one-based.
proc twoSum sum . array[] pair[] .
i = 1
j = len array[]
pair[] = [ ]
repeat
if array[i] + array[j] = sum
pair[] = [ i j ]
return
elif array[i] + array[j] > sum
j -= 1
elif array[i] + array[j] < sum
i += 1
.
until i = j
.
.
numbers[] = [ 0 2 11 19 90 ]
twoSum 21 numbers[] pair[]
print pair[]
- Output:
[ 2 4]
Elixir
defmodule RC do
def two_sum(numbers, sum) do
Enum.with_index(numbers) |>
Enum.reduce_while([], fn {x,i},acc ->
y = sum - x
case Enum.find_index(numbers, &(&1 == y)) do
nil -> {:cont, acc}
j -> {:halt, [i,j]}
end
end)
end
end
numbers = [0, 2, 11, 19, 90]
IO.inspect RC.two_sum(numbers, 21)
IO.inspect RC.two_sum(numbers, 25)
- Output:
[1, 3] []
F#
// Two Sum : Nigel Galloway December 5th., 2017
let fN n i =
let rec fN n e =
match n with
|n::g when n < i -> match List.mapi(fun g i-> (n,i,g)) g |> List.tryFind(fun (n,g,l)->(n+g)=i) with
|Some (n,g,l) -> [e;e+l+1]
|_ -> fN g (e+1)
|_ -> []
fN n 0
printfn "%A" (fN [0; 2; 11; 19; 90] 21)
- Output:
[1; 3]
Factor
USING: combinators fry kernel locals math prettyprint sequences ;
IN: rosetta-code.two-sum
:: two-sum ( seq target -- index-pair )
0 seq length 1 - :> ( x! y! ) [
x y [ seq nth ] bi@ + :> sum {
{ [ sum target = x y = or ] [ f ] }
{ [ sum target > ] [ y 1 - y! t ] }
[ x 1 + x! t ]
} cond
] loop
x y = { } { x y } ? ;
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each
- Output:
{ 1 3 } { } { 0 2 }
A version that maintains a point-free style while still iterating over the numbers once:
USING: accessors arrays assocs combinators.extras hashtables
kernel math math.combinatorics sequences ;
IN: rosetta-code.two-sum
DEFER: (two-sum)
TUPLE: helper sum seq index hash ;
: <two-sum-helper> ( sum seq -- helper )
\ helper new
swap [ >>seq ] keep length <hashtable> >>hash
swap >>sum 0 >>index ;
: no-sum ( helper -- empty ) drop { } ;
: in-bounds? ( helper -- ? )
[ index>> ] [ seq>> length ] bi < ;
: next-sum ( helper -- pair )
dup in-bounds? [ (two-sum) ] [ no-sum ] if ;
: next-index ( helper -- helper ) [ 1 + ] change-index ;
: result ( helper index -- helper ) swap index>> 2array ;
: find-compliment-index ( helper -- helper index/f )
dup [ sum>> ] [ index>> ] [ seq>> nth - ] [ ] quad hash>> at ;
: remember-item ( helper -- helper )
dup [ hash>> ] [ index>> ] [ seq>> nth ] [ index>> ]
quad set-of drop ;
: (two-sum) ( helper -- pair )
remember-item find-compliment-index
[ result ] [ next-index next-sum ] if* ;
: two-sum ( sum seq -- pair ) <two-sum-helper> (two-sum) ;
MAIN: [ { 21 55 11 } [ { 0 2 11 19 90 } two-sum . ] each ]
Forth
CREATE A CELL ALLOT
: A[] ( n -- A[n]) CELLS A @ + @ ;
:NONAME 1- ;
:NONAME R> DROP R> DROP TRUE ;
:NONAME SWAP 1+ SWAP ;
CREATE VTABLE , , ,
: CMP ( n n' -- -1|0|1) - DUP IF DUP ABS / THEN ;
: (TWOSUM) ( addr n n' -- u1 u2 t | f)
>R SWAP A ! 0 SWAP 1- ( lo hi) ( R: n')
BEGIN OVER OVER < WHILE
OVER A[] OVER A[] + R@
CMP 1+ CELLS VTABLE + @ EXECUTE
REPEAT
DROP DROP R> DROP FALSE ;
: TWOSUM ( addr n n' --) [CHAR] [ EMIT
(TWOSUM) IF SWAP 0 .R [CHAR] , EMIT SPACE 0 .R THEN
[CHAR] ] EMIT ;
CREATE TEST0 0 , 2 , 11 , 19 , 90 , DOES> 5 ;
CREATE TEST1 -8 , -2 , 0 , 1 , 5 , 8 , 11 , DOES> 7 ;
TEST0 21 TWOSUM CR
TEST0 25 TWOSUM CR
TEST1 3 TWOSUM CR
TEST1 8 TWOSUM CR
BYE
- Output:
[1, 3] [] [0, 6] [2, 5]
Fortran
program twosum
implicit none
integer, parameter, dimension(5) :: list = (/ 0, 2, 11, 19, 90/)
integer, parameter :: target_val = 21
integer :: nelem
integer :: i, j
logical :: success = .false.
nelem = size(list)
outer:do i = 1,nelem
do j = i+1,nelem
success = list(i) + list(j) == target_val
if (success) exit outer
end do
end do outer
if (success) then
!Just some fancy formatting for nicer output
print('("(",2(i3.1,1X),")",3(A1,i3.1))'), i,j, ":", list(i), "+", list(j), "=", target_val
else
print*, "Failed"
end if
end program twosum
- Output:
( 2 4 ): 2+ 19= 21
FreeBASIC
' FB 1.05.0 Win64
' "a" is the array of sorted non-negative integers
' "b" is the array to contain the result and is assumed to be empty initially
Sub twoSum (a() As UInteger, b() As Integer, targetSum As UInteger)
Dim lb As Integer = LBound(a)
Dim ub As Integer = UBound(a)
If ub = -1 Then Return '' empty array
Dim sum As UInteger
For i As Integer = lb To ub - 1
If a(i) <= targetSum Then
For j As Integer = i + 1 To ub
sum = a(i) + a(j)
If sum = targetSum Then
Redim b(0 To 1)
b(0) = i : b(1) = j
Return
ElseIf sum > targetSum Then
Exit For
End If
Next j
Else
Exit For
End If
Next i
End Sub
Dim a(0 To 4) As UInteger = {0, 2, 11, 19, 90}
Dim b() As Integer
Dim targetSum As UInteger = 21
twoSum a(), b(), targetSum
If UBound(b) = -1 Then
Print "No two numbers were found whose sum is "; targetSum
Else
Print "The numbers with indices"; b(LBound(b)); " and"; b(UBound(b)); " sum to "; targetSum
End If
Print
Print "Press any number to quit"
Sleep
- Output:
The numbers with indices 1 and 3 sum to 21
Go
package main
import "fmt"
func twoSum(a []int, targetSum int) (int, int, bool) {
len := len(a)
if len < 2 {
return 0, 0, false
}
for i := 0; i < len - 1; i++ {
if a[i] <= targetSum {
for j := i + 1; j < len; j++ {
sum := a[i] + a[j]
if sum == targetSum {
return i, j, true
}
if sum > targetSum {
break
}
}
} else {
break
}
}
return 0, 0, false
}
func main() {
a := []int {0, 2, 11, 19, 90}
targetSum := 21
p1, p2, ok := twoSum(a, targetSum)
if (!ok) {
fmt.Println("No two numbers were found whose sum is", targetSum)
} else {
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum)
}
}
- Output:
The numbers with indices 1 and 3 sum to 21
Haskell
Returning first match
twoSum::(Num a,Ord a) => a -> [a] -> [Int]
twoSum num list = sol ls (reverse ls)
where
ls = zip list [0..]
sol [] _ = []
sol _ [] = []
sol xs@((x,i):us) ys@((y,j):vs) = ans
where
s = x + y
ans | s == num = [i,j]
| j <= i = []
| s < num = sol (dropWhile ((<num).(+y).fst) us) ys
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs
main = print $ twoSum 21 [0, 2, 11, 19, 90]
- Output:
[1,3]
Returning all matches
Listing multiple solutions (as zero-based indices) where they exist:
sumTo :: Int -> [Int] -> [(Int, Int)]
sumTo n ns =
let ixs = zip [0 ..] ns
in ixs
>>= ( \(i, x) ->
drop (succ i) ixs
>>= \(j, y) ->
[ (i, j)
| (x + y) == n
]
)
main :: IO ()
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]
Or, resugaring a little – pulling more into the scope of the list comprehension:
sumTo :: Int -> [Int] -> [(Int, Int)]
sumTo n ns =
let ixs = zip [0 ..] ns
in [ (i, j)
| (i, x) <- ixs
, (j, y) <- drop (succ i) ixs
, (x + y) == n ]
main :: IO ()
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]
- Output:
(1,3) (2,5)
Icon and Unicon
Icon and Unicon are ordinal languages, first index is one.
fullimag library used to pretty print lists.
#
# twosum.icn, find two array elements that add up to a given sum
# Dedicated to the public domain
#
link fullimag
procedure main(arglist)
sum := pop(arglist) | 21
L := []
if *arglist > 0 then every put(L, integer(!arglist)) & L := sort(L)
else L := [0, 2, 11, 19, 90]
write(sum)
write(fullimage(L))
write(fullimage(twosum(sum, L)))
end
# assume sorted list, only interested in zero or one solution
procedure twosum(sum, L)
i := 1
j := *L
while i < j do {
try := L[i] + L[j]
if try = sum then return [i,j]
else
if try < sum then
i +:= 1
else
j -:= 1
}
return []
end
- Output:
$ unicon -s twosum.icn -x 21 [0,2,11,19,90] [2,4]
J
So, first off, our basic approach will be to find the sums:
=+/~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
And, check if any of them are our desired value:
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
Except, we want indices here, so let's toss the structure so we can get those:
,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
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:
$21=+/~0 2 11 19 90
5 5
5 5#:I.,21=+/~0 2 11 19 90
1 3
3 1
Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them:
($ #: I.@,)21=+/~0 2 11 19 90
1 3
3 1
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:
($ <@#: 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
Finally, let's start pulling our arguments out using that three verbs combining form:
;{.a:,~($ <@#: I.@,) 21([ = +/~@])0 2 11 19 90
1 3
;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90
1 3
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:
;{. 21 (a:,~ ($ <@#: I.@,)@([ = +/~@]))0 2 11 19 90
1 3
And, let's finish the job, give this a name, and test it out:
twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))
21 twosum 0 2 11 19 90
1 3
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.)
two_sum=:dyad define
sums=. +/~ y
matches=. x = sums
sum_inds=. I. , matches
pair_inds=. ($matches) #: sum_inds
; {. a: ,~ <"1 pair_inds
)
And, testing:
21 two_sum 0 2 11 19 90
1 3
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement:
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.
)
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:
twosum=: ;@{.@(a:,~ ($ <@#: I.@,)@([ = +/~@]))
Alternative approach
An alternative method for identifying and returning non-duplicate indicies of the pairs follows.
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
The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality.
zeroLowerTri=: * [: </~ i.@#
getIdx=: 4 $. $.
twosum_alt=: getIdx@zeroLowerTri@(= +/~)
Testing ...
21 twosum_alt 0 2 11 19 90
1 3
Java
import java.util.Arrays;
public class TwoSum {
public static void main(String[] args) {
long sum = 21;
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;
}
}
[1, 3]
JavaScript
ES5
Nesting concatMap yields the cartesian product of the list with itself, and functions passed to Array.map() have access to the array index in their second argument. Returning [] where the y index is lower than or equal to the x index ignores the 'lower triangle' of the cartesian grid, skipping mirror-image and duplicate number pairs. Returning [] where a sum condition is not met similarly acts as a filter – all of the empty lists in the map result are eliminated by the concat.
(function () {
var concatMap = function (f, xs) {
return [].concat.apply([], xs.map(f))
};
return function (n, xs) {
return concatMap(function (x, ix) {
return concatMap(function (y, iy) {
return iy <= ix ? [] : x + y === n ? [
[ix, iy]
] : []
}, xs)
}, xs)
}(21, [0, 2, 11, 19, 90]);
})();
- Output:
[[1,3]]
ES6
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc.
(() => {
'use strict';
// SUMTWO ----------------------------------------------------------------
// sumTwo :: Int -> [Int] -> [(Int, Int)]
function sumTwo(n, xs) {
const ixs = zip(enumFromTo(0, length(xs) - 1), xs);
return bind(ixs,
([i, x]) => bind(drop(i + 1, ixs),
([j, y]) => (x + y === n) ? [
[i, j]
] : []
)
);
};
// GENERIC FUNCTIONS -----------------------------------------------------
// bind (>>=) :: [a] -> (a -> [b]) -> [b]
const bind = (xs, f) => [].concat.apply([], xs.map(f));
// drop :: Int -> [a] -> [a]
const drop = (n, xs) => xs.slice(n);
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// length :: [a] -> Int
const length = xs => xs.length;
// show :: a -> String
const show = (...x) =>
JSON.stringify.apply(
null, x.length > 1 ? [x[0], null, x[1]] : x
);
// zip :: [a] -> [b] -> [(a,b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => [x, ys[i]]);
// TEST ------------------------------------------------------------------
return show(
sumTwo(21, [0, 2, 11, 19, 90, 10])
);
})();
- Output:
[[1,3],[2,5]]
Jsish
Based on Javascript entry.
/* Two Sum, in Jsish */
function twoSum(target, list) {
var concatMap = function (f, xs) {
return [].concat.apply([], xs.map(f));
};
return function (n, xs) {
return concatMap(function (x, ix) {
return concatMap(function (y, iy) {
return iy <= ix ? [] : x + y === n ? [
[ix, iy]
] : [];
}, xs);
}, xs);
}(target, list);
}
var list = [0, 2, 11, 19, 90];
;list;
;twoSum(21, list);
;list[twoSum(21, list)[0][0]];
;list[twoSum(21, list)[0][1]];
- Output:
prompt$ jsish --U twoSum.jsi list ==> [ 0, 2, 11, 19, 90 ] twoSum(21, list) ==> [ [ 1, 3 ] ] list[twoSum(21, list)[0][0]] ==> 2 list[twoSum(21, list)[0][1]] ==> 19
jq
Works with gojq, the Go implementation of jq.
def twosum($s):
. as $v
| {i: 0, j: ($v|length - 1) }
| until( .i >= .j or $v[.i] + $v[.j] == $s;
if $v[.i] + $v[.j] < $s then .i += 1
else .j -= 1
end)
| if .i >= .j then [] else [.[]] end ; # as required
[0, 2, 11, 19, 90]
| (twosum(21), twosum(25))
- Output:
[1,3] []
Julia
function twosum(v::Vector, s)
i = 1
j = length(v)
while i < j
if v[i] + v[j] == s
return [i, j]
elseif v[i] + v[j] < s
i += 1
else
j -= 1
end
end
return similar(v, 0)
end
@show twosum([0, 2, 11, 19, 90], 21)
- Output:
twosum([0, 2, 11, 19, 90], 21) = [2, 4]
Kotlin
// version 1.1
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? {
if (a.size < 2) return null
var sum: Int
for (i in 0..a.size - 2) {
if (a[i] <= targetSum) {
for (j in i + 1..a.size - 1) {
sum = a[i] + a[j]
if (sum == targetSum) return Pair(i, j)
if (sum > targetSum) break
}
} else {
break
}
}
return null
}
fun main(args: Array<String>) {
val a = intArrayOf(0, 2, 11, 19, 90)
val targetSum = 21
val p = twoSum(a, targetSum)
if (p == null) {
println("No two numbers were found whose sum is $targetSum")
} else {
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum")
}
}
- Output:
The numbers with indices 1 and 3 sum to 21
Liberty BASIC
myArray(0) = 0
myArray(1) = 2
myArray(2) = 11
myArray(3) = 19
myArray(4) = 90
sum = 21
Print twoToSum$("myArray", sum, 0, 4)
End
Function twoToSum$(arrayName$, targetSum, minElement, maxElement)
i = minElement : j = maxElement
While (i < j)
Select Case
Case (Eval(arrayName$;"(";i;")") + Eval(arrayName$;"(";j;")")) < targetSum
i = (i + 1)
Case (Eval(arrayName$;"(";i;")") + Eval(arrayName$;"(";j;")")) > targetSum
j = (j - 1)
Case Else
twoToSum$ = "[";i;",";j;"]"
Exit Function
End Select
Wend
twoToSum$ = "[]"
End Function
- Output:
[1,3]
Lua
Lua uses one-based indexing.
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), ","))
- Output:
2,4
Maple
two_sum := proc(arr, sum)
local i,j,temp:
i,j := 1,numelems(arr):
while (i < j) do
temp := arr[i] + arr[j]:
if temp = sum then
return [i,j]:
elif temp < sum then
i := i + 1:
else
j := j-1:
end if:
end do:
return []:
end proc:
L := Array([0,2,2,11,19,19,90]);
two_sum(L, 21);
- Output:
Note that Maple does 1 based indexing.
[2,5]
Mathematica / Wolfram Language
twoSum[data_List, sum_] :=
Block[{indices = Subsets[Range@Length@data, {2}]},
Cases[indices, _?(Total@data[[#]] == sum &)]]
twoSum[{0, 2, 11, 19, 90}, 21] // TableForm
- Output:
2 4 Note, indexing in Mathematica starts at 1
MiniScript
twoSum = function(numbers, sum)
// Make a map of values to their indices in the numbers array
// as we go, so we will know when we've found a match.
map = {}
for i in numbers.indexes
key = sum - numbers[i]
if map.hasIndex(key) then return [map[key], i]
map[numbers[i]] = i
end for
end function
print twoSum([0, 2, 11, 19, 90], 21)
Output:
[1, 3]
Modula-2
MODULE TwoSum;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,ReadChar;
TYPE
Pair = RECORD
f,s : INTEGER;
END;
PROCEDURE TwoSum(CONST arr : ARRAY OF INTEGER; CONST sum : INTEGER) : Pair;
VAR i,j,temp : INTEGER;
BEGIN
i := 0;
j := HIGH(arr)-1;
WHILE i<=j DO
temp := arr[i] + arr[j];
IF temp=sum THEN
RETURN Pair{i,j};
END;
IF temp<sum THEN
INC(i);
ELSE
DEC(j);
END;
END;
RETURN Pair{-1,-1};
END TwoSum;
VAR
buf : ARRAY[0..63] OF CHAR;
arr : ARRAY[0..4] OF INTEGER;
res : Pair;
BEGIN
arr[0]:=0;
arr[1]:=2;
arr[2]:=11;
arr[3]:=19;
arr[4]:=90;
res := TwoSum(arr, 21);
FormatString("[%i, %i]\n", buf, res.f, res.s);
WriteString(buf);
ReadChar;
END TwoSum.
Nim
proc twoSum(src: openarray[int], target: int): array[2, int] =
if src.len < 2:
return
for base in 0 .. (src.len - 2):
for ext in (base + 1) ..< src.len:
if src[base] + src[ext] == target:
result[0] = base
result[1] = ext
proc main =
var data0 = [0, 2, 11, 19, 90]
var res = twoSum(data0, 21)
assert(res == [1, 3])
var data1 = [0, 2, 11, 19, 90]
res = twoSum(data1, 22)
assert(res == [0, 0])
var data2 = [1]
res = twoSum(data2, 22)
assert(res == [0, 0])
var data3 = [1, 99]
res = twoSum(data3, 100)
assert(res == [0, 1])
var data4 = [1, 99]
res = twoSum(data4, 101)
assert(res == [0, 0])
main()
Objeck
class TwoSum {
function : Main(args : String[]) ~ Nil {
sum := 21;
arr := [0, 2, 11, 19, 90];
Print(TwoSum(arr, sum));
}
function : TwoSum(a : Int[], target : Int) ~ Int[] {
i := 0;
j := a->Size() - 1;
while (i < j) {
sum := a[i] + a[j];
if(sum = target) {
r := Int->New[2];
r[0] := i;
r[1] := j;
return r;
};
if (sum < target) {
i++;
}
else {
j--;
};
};
return Nil;
}
function : Print(r : Int[]) ~ Nil {
'['->Print();
each(i : r) {
r[i]->Print();
if(i + 1 < r->Size()) {
','->Print();
};
};
']'->PrintLine();
}
}
Output:
[1,3]
OCaml
let get_sums ~numbers ~sum =
let n = Array.length numbers in
let res = ref [] in
for i = 0 to n - 2 do
for j = i + 1 to n - 1 do
if numbers.(i) + numbers.(j) = sum then
res := (i, j) :: !res
done
done;
!res
let () =
let numbers = [| 0; 2; 11; 19; 90 |]
and sum = 21
in
let res = get_sums ~numbers ~sum in
List.iter (fun (i, j) ->
Printf.printf "# Found: %d %d\n" i j
) res
Will return all possible sums, not just the first one found.
- Output:
$ ocaml two_sum.ml # Found: 1 3
ooRexx
a=.array~of( -5, 26, 0, 2, 11, 19, 90)
x=21
n=0
do i=1 To a~items
Do j=i+1 To a~items
If a[i]+a[j]=x Then Do
Say '['||i-1||','||j-1||']'
n=n+1
End
End
End
If n=0 Then
Say '[] - no items found'
- Output:
[0,1] [3,5]
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 ).
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.
- 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
use strict;
use warnings;
use feature 'say';
sub two_sum{
my($sum,@numbers) = @_;
my $i = 0;
my $j = $#numbers - 1;
my @indices;
while ($i < $j) {
if ($numbers[$i] + $numbers[$j] == $sum) { push @indices, ($i, $j); $i++; }
elsif ($numbers[$i] + $numbers[$j] < $sum) { $i++ }
else { $j-- }
}
return @indices
}
my @numbers = <0 2 11 19 90>;
my @indices = two_sum(21, @numbers);
say join(', ', @indices) || 'No match';
@indices = two_sum(25, @numbers);
say join(', ', @indices) || 'No match';
- Output:
1, 3 No match
Phix
function twosum(sequence s, integer t) for i=1 to length(s) do for j=i+1 to length(s) do if s[i]+s[j]=t then return {i,j} end if end for end for return {} end function ?twosum({0, 2, 11, 19, 90},21)
function twosum(sequence numbers, integer total) integer i=1, j=length(numbers) while i<j do switch compare(numbers[i]+numbers[j],total) do case -1: i += 1 case 0: return {i, j} case +1: j -= 1 end switch end while return {} end function
- Output:
Phix uses 1-based indexes
{2,4}
Phixmonti
include ..\Utilitys.pmt
def two_sum /# arr num -- n #/
var num
1 var i
len var j
true
while
i get swap j get rot + >ps
tps num == if
ps> drop j get swap i get rot 2 tolist false
else
ps> num < if i 1 + var i else j 1 - var j endif true
endif
i j < and
endwhile
len 2 > if drop ( ) endif
enddef
( 0 2 11 19 90 )
21 two_sum ?
25 two_sum ?
- Output:
[2, 19] [] === Press any key to exit ===
PicoLisp
(de twosum (Lst N)
(for ((I . A) Lst A (cdr A))
(T
(for ((J . B) (cdr Lst) B (cdr B))
(T (= N (+ (car A) (car B)))
(cons I (inc J)) ) )
@ ) ) )
(println
(twosum (0 2 11 19 90) 21)
(twosum (-3 -2 0 1 5 8 11) 17)
(twosum (-8 -2 -1 1 5 9 11) 0) )
- Output:
(2 . 4) NIL (3 . 4)
PowerShell
Lazy, very lazy.
$numbers = @(0, 2, 11, 19, 90)
$sum = 21
$totals = for ($i = 0; $i -lt $numbers.Count; $i++)
{
for ($j = $numbers.Count-1; $j -ge 0; $j--)
{
[PSCustomObject]@{
FirstIndex = $i
SecondIndex = $j
TargetSum = $numbers[$i] + $numbers[$j]
}
}
}
$totals | Where-Object TargetSum -EQ $sum |
Select-Object -First 1 `
-Property @{
Name = "Sum"
Expression = { $_.TargetSum }
},
@{
Name = "Indices"
Expression = { @($_.FirstIndex, $_.SecondIndex) }
}
- Output:
Sum Indices --- ------- 21 {1, 3}
Python
def two_sum(arr, num):
i = 0
j = len(arr) - 1
while i < j:
if arr[i] + arr[j] == num:
return (i, j)
if arr[i] + arr[j] < num:
i += 1
else:
j -= 1
return None
numbers = [0, 2, 11, 19, 90]
print(two_sum(numbers, 21))
print(two_sum(numbers, 25))
or, in terms of itertools.product:
'''Finding two integers that sum to a target value.'''
from itertools import (product)
# sumTwo :: [Int] -> Int -> [(Int, Int)]
def sumTwo(xs):
'''All the pairs of integers in xs which
sum to n.
'''
def go(n):
ixs = list(enumerate(xs))
return [
(fst(x), fst(y)) for (x, y) in (
product(ixs, ixs[1:])
) if fst(x) < fst(y) and n == snd(x) + snd(y)
]
return lambda n: go(n)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests'''
xs = [0, 2, 11, 19, 90, 10]
print(
fTable(
'The indices of any two integers drawn from ' + repr(xs) +
'\nthat sum to a given value:\n'
)(str)(
lambda x: str(x) + ' = ' + ', '.join(
['(' + str(xs[a]) + ' + ' + str(xs[b]) + ')' for a, b in x]
) if x else '(none)'
)(
sumTwo(xs)
)(enumFromTo(10)(25))
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]
# snd :: (a, b) -> b
def snd(tpl):
'''Second member of a pair.'''
return tpl[1]
# DISPLAY -------------------------------------------------
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
The indices of any two integers drawn from [0, 2, 11, 19, 90, 10] that sum to a given value: 10 -> [(0, 5)] = (0 + 10) 11 -> [(0, 2)] = (0 + 11) 12 -> [(1, 5)] = (2 + 10) 13 -> [(1, 2)] = (2 + 11) 14 -> (none) 15 -> (none) 16 -> (none) 17 -> (none) 18 -> (none) 19 -> [(0, 3)] = (0 + 19) 20 -> (none) 21 -> [(1, 3), (2, 5)] = (2 + 19), (11 + 10) 22 -> (none) 23 -> (none) 24 -> (none) 25 -> (none)
or, a little more parsimoniously (not generating the entire cartesian product), in terms of concatMap:
'''Finding two integers that sum to a target value.'''
from itertools import chain
# sumTwo :: Int -> [Int] -> [(Int, Int)]
def sumTwo(n, xs):
'''All the pairs of integers in xs which
sum to n.
'''
def go(vs):
return [vs[0]] if n == sum(vs[1]) else []
ixs = list(enumerate(xs))
return list(
bind(ixs)(
lambda ix: bind(ixs[ix[0]:])(
lambda jy: go(tuple(zip(*(ix, jy))))
)
)
)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests'''
for n in [21, 25]:
print(
sumTwo(n, [0, 2, 11, 19, 90, 10])
)
# GENERIC -------------------------------------------------
# bind (>>=) :: [a] -> (a -> [b]) -> [b]
def bind(xs):
'''List monad injection operator.
Two computations sequentially composed,
with any value produced by the first
passed as an argument to the second.
'''
return lambda f: list(
chain.from_iterable(
map(f, xs)
)
)
if __name__ == '__main__':
main()
- Output:
[(1, 3), (2, 5)] []
Quackery
So… I initially misread the task as "return the two integers" and then realised it was "…the indices of…", but that's OK — it just meant writing an extra word to find the indices, given the numbers.
The last three lines of task
are in case the two integers found by twosum
are equal - in which case, as find
finds the first instance in the array and the array is sorted, we can safely take the index plus one as the second index.
[ 0 peek ] is first ( [ --> n )
[ -1 peek ] is last ( [ --> n )
[ 1 split nip ] is top ( [ --> [ )
[ -1 split drop ] is tail ( [ --> [ )
[ temp put
[ dup size 2 < iff
[ drop [] ] done
dup first over last +
temp share -
dup 0 = iff
[ drop dup first
swap last join ] done
0 < iff top else tail
again ]
temp release ] is twosum ( [ n --> [ )
[ over temp put
twosum
[] swap
witheach
[ temp share find join ]
temp release
dup [] != if
[ dup unpack = if
[ behead 1+ join ] ] ] is task ( [ n --> [ )
' [ 0 2 11 19 20 ] 21 task echo cr
' [ 0 2 11 19 20 ] 25 task echo cr
' [ 0 2 12 12 20 ] 24 task echo cr
- Output:
[ 1 3 ] [ ] [ 2 3 ]
R
numbers<- c(0,2,11,19,28,90)
two_sum<- function(numbers,s){
all_sums <- outer(numbers,numbers,"+")==s
all_sums[lower.tri(all_sums)] <- NA
which(all_sums,arr.ind = T) #first index is in the "row" column, and second index is in the "col" column
}
#In R, index begins from 0
print(two_sum(numbers,21)) #should return 2 4
cat("\n")
print(two_sum(numbers,24)) #should return nothing
cat("\n")
print(two_sum(numbers,30)) #should return 3 4 and 2 5
Output
row col [1,] 2 4 row col row col [1,] 3 4 [2,] 2 5
Racket
#lang racket/base
(define (two-sum v m)
(let inr ((l 0) (r (sub1 (vector-length v))))
(and
(not (= l r))
(let ((s (+ (vector-ref v l) (vector-ref v r))))
(cond [(= s m) (list l r)] [(> s m) (inr l (sub1 r))] [else (inr (add1 l) r)])))))
(module+ test
(require rackunit)
;; test cases
;; no output indicates returns are as expected
(check-equal? (two-sum #( 0 2 11 19 90) 21) '(1 3))
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6))
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f)
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))
Raku
(formerly Perl 6)
Procedural
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;
- Output:
(1 3) Nil
Functional
The two versions differ only in how one 'reads' the notional flow of processing: left-to-right versus right-to-left.
Both return all pairs that sum to the target value, not just the first (e.g. for input of 0 2 10 11 19 90
would get indices 1/4 and 2/3).
sub two-sum-lr (@a, $sum) {
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique
(
(
(^@a X ^@a) Z=> (@a X+ @a)
).grep($sum == *.value)>>.keys
.map:{ .split(' ').sort.join(' ')}
).unique
}
sub two-sum-rl (@a, $sum) {
# unique map {.split(' ').sort.join(' ')}, keys %(grep {.value == $sum}, ((^@a X ^@a) Z=> (@a X+ @a)))
unique
map {.split(' ').sort.join(' ')},
keys %(
grep {.value == $sum}, (
(^@a X ^@a) Z=> (@a X+ @a)
)
)
}
my @a = <0 2 11 19 90>;
for 21, 25 {
say two-sum-rl(@a, $_);
say two-sum-lr(@a, $_);
}
- Output:
(1 3) (1 3) () ()
REXX
version 1
/* REXX */
list='-5 26 0 2 11 19 90'
Do i=0 By 1 Until list=''
Parse Var list a.i list
End
n=i
x=21
z=0
do i=0 To n
Do j=i+1 To n
s=a.i+a.j
If s=x Then Do
z=z+1
Say '['i','j']' a.i a.j s
End
End
End
If z=0 Then
Say '[] - no items found'
Else
Say z 'solutions found'
- Output:
[0,1] -5 26 21 [3,5] 2 19 21 2 solutions found
version 2
All solutions are listed (if any), along with a count of the number of solutions.
Also, it's mentioned that the indices are zero─based, and formatted solutions are shown.
The list of numbers can be in any format, not just integers. Also, they need not be unique.
The list of integers needn't be sorted.
A numeric digits 500 statement was added just in case some humongous numbers were entered.
No verification was performed to ensure that all items in the list were numeric.
A little extra code was added to have the output columns aligned.
/*REXX program finds two numbers in a list of numbers that sum to a particular target.*/
numeric digits 500 /*be able to handle some larger numbers*/
parse arg targ list /*obtain optional arguments from the CL*/
if targ='' | targ="," then targ= 21 /*Not specified? Then use the defaults*/
if list='' | list="," then list= 0 2 11 19 90 /* " " " " " " */
say 'the list: ' list /*echo the list to the terminal*/
say 'the target sum: ' targ /* " " target sum " " " */
w= 0; sol= 0 /*width; # of solutions found (so far)*/
do #=0 for words(list); _=word(list, #+1) /*examine the list, construct an array.*/
@.#= _; w= max(w, length(_) ) /*assign a number to an indexed array. */
end /*#*/ /*W: the maximum width of any number. */
L= length(#) /*L: " " " " " index. */
@solution= 'a solution: zero─based indices ' /*a SAY literal for space conservation.*/
say /* [↓] look for sum of 2 numbers=target*/
do a=0 for # /*scan up to the last number in array. */
do b=a+1 to #-1; if @.a + @.b\=targ then iterate /*Sum not correct? Skip.*/
sol= sol + 1 /*bump count of the number of solutions*/
say @solution center( "["right(a, L)',' right(b, L)"]", L+L+5) ,
right(@.a, w*4) " + " right(@.b, w) ' = ' targ
end /*b*/ /*show the 2 indices and the summation.*/
end /*a*/
say
if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/
say 'number of solutions found: ' sol /*stick a fork in it, we're all done. */
- output when using the default inputs:
the list: 0 2 11 19 90 the target sum: 21 a solution: zero─based indices [1, 3] 2 + 19 = 21 number of solutions found: 1
- output when using the input of: 21 -78 -5 1 0 -1 -4 11 14 23.5 5 +3 2. 18 -2.50 +2 16 19 018 23 24 25 26 199 2 3 17 +18 19 03 3 .18e2
the list: -78 -5 1 0 -1 -4 11 14 23.5 5 +3 2. 18 -2.50 +2 16 19 018 23 24 25 26 199 2 3 17 +18 19 03 3 .18e2 the target sum: 21 a solution: zero─based indices [ 1, 21] -5 + 26 = 21 a solution: zero─based indices [ 5, 20] -4 + 25 = 21 a solution: zero─based indices [ 8, 13] 23.5 + -2.50 = 21 a solution: zero─based indices [ 9, 15] 5 + 16 = 21 a solution: zero─based indices [10, 12] +3 + 18 = 21 a solution: zero─based indices [10, 17] +3 + 018 = 21 a solution: zero─based indices [10, 26] +3 + +18 = 21 a solution: zero─based indices [10, 30] +3 + .18e2 = 21 a solution: zero─based indices [11, 16] 2. + 19 = 21 a solution: zero─based indices [11, 27] 2. + 19 = 21 a solution: zero─based indices [12, 24] 18 + 3 = 21 a solution: zero─based indices [12, 28] 18 + 03 = 21 a solution: zero─based indices [12, 29] 18 + 3 = 21 a solution: zero─based indices [14, 16] +2 + 19 = 21 a solution: zero─based indices [14, 27] +2 + 19 = 21 a solution: zero─based indices [16, 23] 19 + 2 = 21 a solution: zero─based indices [17, 24] 018 + 3 = 21 a solution: zero─based indices [17, 28] 018 + 03 = 21 a solution: zero─based indices [17, 29] 018 + 3 = 21 a solution: zero─based indices [23, 27] 2 + 19 = 21 a solution: zero─based indices [24, 26] 3 + +18 = 21 a solution: zero─based indices [24, 30] 3 + .18e2 = 21 a solution: zero─based indices [26, 28] +18 + 03 = 21 a solution: zero─based indices [26, 29] +18 + 3 = 21 a solution: zero─based indices [28, 30] 03 + .18e2 = 21 a solution: zero─based indices [29, 30] 3 + .18e2 = 21 number of solutions found: 26
Ring
# Project : Two Sum
numbers = [0, 2, 11, 19, 90]
sum = 21
see "order list: "
for n=1 to len(numbers)
see " " + numbers[n]
next
see " (using a zero index.)" + nl
for n=1 to len(numbers)
for m=n to len(numbers)
if numbers[n] + numbers[m] = sum
see "target sum: " + sum + nl
see "a solution: ["
see "" + (n-1) + " " + (m-1) + "]" + nl
ok
next
next
Output:
order list: 0 2 11 19 90 (using a zero index.) target sum: 21 a solution: [1 3]
RPL
≪ → array sum
≪ { }
1 array SIZE FOR j
array j 0 PUT
sum array j GET -
IF POS THEN
j LAST
IF DUP2 > THEN SWAP END
R→C
IF DUP2 POS THEN DROP ELSE + END
END NEXT
≫ ≫ ‘TWOSUM’ STO
{0 2 11 19 90} 21 TWOSUM {0 2 11 19 90} 22 TWOSUM {0 2 3 3 4 11 17 17 18 19 90} 21 TWOSUM
- Output:
3: { (2,4) } 2: { } 1: { (2,10) (3,9) (4,9) (5,7) (5,8) }
Ruby
def two_sum(numbers, sum)
numbers.each_with_index do |x,i|
if j = numbers.index(sum - x) then return [i,j] end
end
[]
end
numbers = [0, 2, 11, 19, 90]
p two_sum(numbers, 21)
p two_sum(numbers, 25)
- Output:
[1, 3] []
When the size of the Array is bigger, the following is more suitable.
def two_sum(numbers, sum)
numbers.each_with_index do |x,i|
key = sum - x
if j = numbers.bsearch_index{|y| key<=>y}
return [i,j]
end
end
[]
end
Rust
use std::cmp::Ordering;
use std::ops::Add;
fn two_sum<T>(arr: &[T], sum: T) -> Option<(usize, usize)>
where
T: Add<Output = T> + Ord + Copy,
{
if arr.len() == 0 {
return None;
}
let mut i = 0;
let mut j = arr.len() - 1;
while i < j {
match (arr[i] + arr[j]).cmp(&sum) {
Ordering::Equal => return Some((i, j)),
Ordering::Less => i += 1,
Ordering::Greater => j -= 1,
}
}
None
}
fn main() {
let arr = [0, 2, 11, 19, 90];
let sum = 21;
println!("{:?}", two_sum(&arr, sum));
}
- Output:
Some((1, 3))
Scala
import java.util
object TwoSum extends App {
val (sum, arr)= (21, Array(0, 2, 11, 19, 90))
println(util.Arrays.toString(twoSum(arr, sum)))
private def twoSum(a: Array[Int], target: Long): Array[Int] = {
var (i, j) = (0, a.length - 1)
while (i < j) {
val sum = a(i) + a(j)
if (sum == target) return Array[Int](i, j)
if (sum < target) i += 1 else j -= 1
}
null
}
}
- Output:
See it running in your browser by ScalaFiddle (JavaScript, non JVM) or by Scastie (JVM).
Sidef
func two_sum(numbers, sum) {
var (i, j) = (0, numbers.end)
while (i < j) {
given (sum <=> numbers[i]+numbers[j]) {
when (-1) { --j }
when (+1) { ++i }
default { return [i, j] }
}
}
return []
}
say two_sum([0, 2, 11, 19, 90], 21)
say two_sum([0, 2, 11, 19, 90], 25)
- Output:
[1, 3] []
Stata
Notice that array indexes start at 1 in Stata.
function find(a, x) {
i = 1
j = length(a)
while (i<j) {
s = a[i]+a[j]
if (s<x) i++
else if (s>x) j--
else return((i,j))
}
}
find((0,2,11,19,90),21)
1 2
+---------+
1 | 2 4 |
+---------+
Uiua
Works by using ⊞f. to form a cross product (similar to APL's ∘.f⍨). The resulting additions are multiplied with a mask of the upper right half (⊞>.⇡⧻) to remove extraneous answers.
f ← ⊚=×⊞>.⇡⧻.⊞+.
f 0_2_11_19_90 21
- Output:
╭─ ╷ 1 3 ╯
Vala
void main() {
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0;
for (i = 0; i < 4; i++) {
for ( j = i+1; j < 5; j++) {
if (arr[i] + arr[j] == sum) {
print("[%d,%d]",i,j);
check = 1;
break;
}
}
}
if (check == 0)
print("[]");
}
- Output:
[1,3]
VBA
Option Explicit
Function two_sum(a As Variant, t As Integer) As Variant
Dim i, j As Integer
i = 0
j = UBound(a)
Do While (i < j)
If (a(i) + a(j) = t) Then
two_sum = Array(i, j)
Exit Function
ElseIf (a(i) + a(j) < t) Then i = i + 1
ElseIf (a(i) + a(j) > t) Then j = j - 1
End If
Loop
two_sum = Array()
End Function
Sub prnt(a As Variant)
If UBound(a) = 1 Then
Selection.TypeText Text:="(" & a(0) & ", " & a(1) & ")" & vbCrLf
Else
Selection.TypeText Text:="()" & vbCrLf
End If
End Sub
Sub main()
Call prnt(two_sum(Array(0, 2, 11, 19, 90), 21))
Call prnt(two_sum(Array(-8, -2, 0, 1, 5, 8, 11), 3))
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17))
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0))
End Sub
- Output:
(1, 3) (0, 6) () (2, 3)
Visual Basic .NET
Module Module1
Function TwoSum(numbers As Integer(), sum As Integer) As Integer()
Dim map As New Dictionary(Of Integer, Integer)
For index = 1 To numbers.Length
Dim i = index - 1
' see if the complement is stored
Dim key = sum - numbers(i)
If map.ContainsKey(key) Then
Return {map(key), i}
End If
map.Add(numbers(i), i)
Next
Return Nothing
End Function
Sub Main()
Dim arr = {0, 2, 1, 19, 90}
Const sum = 21
Dim ts = TwoSum(arr, sum)
Console.WriteLine(If(IsNothing(ts), "no result", $"{ts(0)}, {ts(1)}"))
End Sub
End Module
- Output:
1, 3
V (Vlang)
fn two_sum(a []int, target_sum int) (int, int, bool) {
len := a.len
if len < 2 {return 0, 0, false}
for i in 0..len - 1 {
if a[i] <= target_sum {
for j in i + 1..len {
sum := a[i] + a[j]
if sum == target_sum {return i, j, true}
if sum > target_sum {break}
}
}
else {break}
}
return 0, 0, false
}
fn main() {
a := [0, 2, 11, 19, 90]
target_sum := 21
p1, p2, ok := two_sum(a, target_sum)
if !ok {println("No two numbers were found whose sum is $target_sum")}
else {println("The numbers with indices $p1 and $p2 sum to $target_sum")}
}
- Output:
The numbers with indices 1 and 3 sum to 21
X86 Assembly
section .data
outputArr dd 0,0,0
inputArr dd 5,0,2,11,19,90
section .text
global _main
_main:
mov ebp, esp
mov eax, 21 ;num we search for
push inputArr
call func
add esp, 4
ret
func:
mov esi, [ebp - 4];get arr address from stack
add esi, 4 ;esi now points to the first element instead of the length
mov edx, 0 ;i
mov ecx, [esi - 4] ;j
dec ecx ;counting starts from 0
looping:
cmp edx, ecx ;while i < j
jge return
mov ebx, [esi + edx * 4]
add ebx, [esi + ecx * 4] ;inputArr[i] + inputArr[j]
cmp ebx, eax ;inputArr[i] + inputArr[j] (==|<|else) eax
je end ;==
jl i ;<
dec ecx ;else j--
jmp looping
i:
inc edx ;i++
jmp looping
end:
mov eax, 2 ;if we find a combination our array has a length of 2
mov [outputArr], eax ;length is in the first 4 byte cell
mov [outputArr + 4], edx ;i
mov [outputArr + 8], ecx ;j
return:
mov eax, outputArr ;address of outputArr is returned in eax
ret
Wren
var twosum = Fn.new { |a, n|
var c = a.count
if (c < 2) return []
for (i in 0...c-1) {
for (j in i+1...c) {
var s = a[i] + a[j]
if (s == n) return [i, j]
if (s > n) break
}
}
return []
}
var a = [0, 2, 11, 19, 90]
System.print("Numbers: %(a)\n")
for (n in [21, 25, 90]) {
var pair = twosum.call(a, n)
if (pair.count == 2) {
System.print("Indices: %(pair) sum to %(n) (%(a[pair[0]]) + %(a[pair[1]]) = %(n))")
} else {
System.print("No pairs of the above numbers sum to %(n).")
}
System.print()
}
- Output:
Numbers: [0, 2, 11, 19, 90] Indices: [1, 3] sum to 21 (2 + 19 = 21) No pairs of the above numbers sum to 25. Indices: [0, 4] sum to 90 (0 + 90 = 90)
XPL0
Test cases from Algol 68.
proc TwoSum(Size, Array, Sum);
int Size, Array, Sum, I, J;
[Text(0, "[");
for I:= 0 to Size-1 do
for J:= I+1 to Size-1 do
if Array(I) + Array(J) = Sum then
[IntOut(0, I); Text(0, ", "); IntOut(0, J);
J:= Size; I:= Size;
];
Text(0, "]^m^j");
];
[TwoSum(5, [ 0, 2, 11, 19, 90], 21); \ should be [1, 3]
TwoSum(7, [-8, -2, 0, 1, 5, 8, 11], 3); \ should be [0, 6] (or [1, 4])
TwoSum(7, [-3, -2, 0, 1, 5, 8, 11], 17); \ should be []
TwoSum(7, [-8, -2, -1, 1, 5, 9, 11], 0); \ should be [2, 3]
]
- Output:
[1, 3] [0, 6] [] [2, 3]
Yabasic
// Rosetta Code problem: http://rosettacode.org/wiki/Two_sum
// by Galileo, 04/2022
Sub twoSum (a(), b(), targetSum)
local ub, sum, i, j
ub = arraysize(a(), 1)
For i = 1 To ub - 1
If a(i) <= targetSum Then
For j = i + 1 To ub
sum = a(i) + a(j)
If sum = targetSum Then
Redim b(2)
b(1) = i : b(2) = j
Return
ElsIf sum > targetSum Then
break
EndIf
Next j
Else
break
EndIf
Next i
End Sub
Dim a(5)
Dim b(1)
data 0, 2, 11, 19, 90
for n = 1 to 5 : read a(n) : next
targetSum = 21
twoSum(a(), b(), targetSum)
If arraysize(b(), 1) = 1 Then
Print "No two numbers were found whose sum is ", targetSum
Else
Print "The numbers with indices ", b(1), " and ", b(2), " sum to ", targetSum
End If
- Output:
The numbers with indices 2 and 4 sum to 21 ---Program done, press RETURN---
Zig
Works with: 0.11.x, 0.12.0-dev.1389+42d4d07ef
pub fn sumsUpTo(comptime T: type, input: []const T, target_sum: T) ?struct { usize, usize } {
if (input.len <= 1) return null;
return result: for (input[0 .. input.len - 1], 0..) |left, left_i| {
if (left > target_sum) break :result null;
const offset = left_i + 1;
for (input[offset..], offset..) |right, right_i| {
const current_sum = left + right;
if (current_sum < target_sum) continue;
if (current_sum == target_sum) break :result .{ left_i, right_i };
if (current_sum > target_sum) break;
}
} else null;
}
const std = @import("std");
pub fn main() std.fs.File.WriteError!void {
const stdout = std.io.getStdOut();
const stdout_w = stdout.writer();
const stderr = std.io.getStdErr();
const stderr_w = stderr.writer();
const a = [_]u32{ 0, 2, 11, 19, 90 };
const target_sum: u32 = 21;
const optional_indexes = sumsUpTo(u32, &a, target_sum);
if (optional_indexes) |indexes| {
try stdout_w.print("Result: [{d}, {d}].\n", .{ indexes[0], indexes[1] });
} else {
try stderr_w.print("Numbers with sum {d} were not found!\n", .{target_sum});
}
}
- Output:
Result: [1, 3].
zkl
The sorted O(n) no external storage solution:
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;
}
}
twoSum2(21,T(0,2,11,19,90)).println();
twoSum2(25,T(0,2,11,19,90)).println();
- Output:
L(1,3) False
The unsorted O(n!) all solutions solution:
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)) })
}
twoSum2(21,T(0,2,11,19,90,21)).println();
twoSum2(25,T(0,2,11,19,90,21)).println();
- Output:
L(L(0,5),L(1,3)) L()
- Draft Programming Tasks
- Arithmetic operations
- Clarified and Needing Review
- 11l
- AArch64 Assembly
- Action!
- Aime
- ALGOL 68
- APL
- AppleScript
- ARM Assembly
- Arturo
- AutoHotkey
- AWK
- Befunge
- C
- C sharp
- C++
- D
- Dart
- Delphi
- System.SysUtils
- System.Generics.Collections
- EasyLang
- Elixir
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jsish
- Jq
- Julia
- Kotlin
- Liberty BASIC
- Lua
- Maple
- Mathematica
- Wolfram Language
- MiniScript
- Modula-2
- Nim
- Objeck
- OCaml
- OoRexx
- Pascal
- Perl
- Phix
- Phixmonti
- PicoLisp
- PowerShell
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Sidef
- Stata
- Uiua
- Vala
- VBA
- Visual Basic .NET
- V (Vlang)
- X86 Assembly
- Wren
- XPL0
- Yabasic
- Zig
- Zkl