Two sum: Difference between revisions
Content deleted Content added
Added XPL0 example. |
Added Uiua |
||
(17 intermediate revisions by 13 users not shown) | |||
Line 1:
{{
Line 22:
{{trans|Python}}
<
V i = 0
V j = arr.len - 1
Line 36:
V numbers = [0, 2, 11, 19, 90]
print(two_sum(numbers, 21))
print(two_sum(numbers, 25))</
{{out}}
Line 42:
[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!}}==
<
INT i
Line 98 ⟶ 265:
Test(a,5,22)
Test(b,11,21)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Two_sum.png Screenshot from Atari 8-bit computer]
Line 116 ⟶ 283:
=={{header|Aime}}==
<
index x;
list l;
Line 128 ⟶ 295:
break;
}
}</
{{Out}}
<pre>1 3</pre>
Line 134 ⟶ 301:
=={{header|ALGOL 68}}==
{{trans|Lua}}
<
# if there isn't a pair of numbers that summs to sum, an empty array is returned #
PRIO TWOSUM = 9;
Line 170 ⟶ 337:
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] #</
{{out}}
<pre>
Line 190 ⟶ 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 (⊃).
<syntaxhighlight lang="apl">
⎕io ← 0 ⍝ sets index origin to 0
ts ← {⊃⍸ ⍵= 0.1@(⍸∘.=⍨⍳≢⍺) ∘.+⍨ ⍺}
⎕ ← 0 2 11 19 90 ts 21 ⍝ should be 1 3
</syntaxhighlight>
{{out}}
<pre>
Line 212 ⟶ 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 :-)
<
-- twoSum :: Int -> [Int] -> [(Int, Int)]
Line 358 ⟶ 525:
end repeat
return lst
end zip</
{{Out}}
<syntaxhighlight lang
----
Line 366 ⟶ 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.
<
script o
property lst : givenNumbers
Line 391 ⟶ 558:
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}}
<
{}
{{1, 11}, {2, 8}, {2, 9}, {2, 10}, {3, 8}, {3, 9}, {3, 10}, {4, 7}, {5, 6}}</
=={{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}}==
<
i := 1, j := a.MaxIndex()
while(i < j){
Line 410 ⟶ 761:
}
return "not found"
}</
Examples:<
Outputs:<pre>2,4</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f TWO_SUM.AWK
BEGIN {
Line 440 ⟶ 791:
return("[]")
}
</syntaxhighlight>
{{out}}
<pre>
Line 448 ⟶ 799:
=={{header|Befunge}}==
<
>&:0\`#v_00g:1+00p6p
v >$&50p110p020p
Line 463 ⟶ 814:
>:#,_@ 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:
<pre>
Line 473 ⟶ 824:
=={{header|C}}==
<syntaxhighlight lang="c">
#include<stdio.h>
Line 495 ⟶ 846:
return 0;
}
</syntaxhighlight>
Output :
<pre>
Line 502 ⟶ 853:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 534 ⟶ 885:
}
}
</syntaxhighlight>
{{out}}
<pre>1, 3</pre>
Line 540 ⟶ 891:
=={{header|C++}}==
{{trans|C#}}
<
#include <map>
#include <tuple>
Line 574 ⟶ 925:
return 0;
}</
{{out}}
<pre>{1,3}</pre>
=={{header|D}}==
<
void main() {
Line 616 ⟶ 967:
return [];
}</
{{out}}
<pre>[1, 3]</pre>
=={{header|Dart}}==
<syntaxhighlight lang="text">
main() {
var a = [1,2,3,4,5];
Line 650 ⟶ 1,001:
</syntaxhighlight>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.Generics.Collections}}
{{Trans|Python}}
<syntaxhighlight lang="delphi">
program Two_Sum;
Line 692 ⟶ 1,043:
Writeln('(', i, ',', j, ')');
Readln;
end.</
{{out}}
<pre>
(1,3)
</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}}==
<
def two_sum(numbers, sum) do
Enum.with_index(numbers) |>
Line 713 ⟶ 1,091:
numbers = [0, 2, 11, 19, 90]
IO.inspect RC.two_sum(numbers, 21)
IO.inspect RC.two_sum(numbers, 25)</
{{out}}
Line 722 ⟶ 1,100:
=={{header|F_Sharp|F#}}==
<
// Two Sum : Nigel Galloway December 5th., 2017
let fN n i =
Line 733 ⟶ 1,111:
fN n 0
printfn "%A" (fN [0; 2; 11; 19; 90] 21)
</syntaxhighlight>
{{out}}
<pre>
Line 740 ⟶ 1,118:
=={{header|Factor}}==
<
IN: rosetta-code.two-sum
Line 753 ⟶ 1,131:
x y = { } { x y } ? ;
{ 21 55 11 } [ '[ { 0 2 11 19 90 } _ two-sum . ] call ] each</
{{out}}
<pre>
Line 760 ⟶ 1,138:
{ 0 2 }
</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}}==
{{works with|Gforth|0.7.3}}
<
: A[] ( n -- A[n]) CELLS A @ + @ ;
:NONAME 1- ;
Line 786 ⟶ 1,206:
TEST1 3 TWOSUM CR
TEST1 8 TWOSUM CR
BYE</
{{out}}
<pre>[1, 3]
Line 794 ⟶ 1,214:
=={{header|Fortran}}==
<
implicit none
Line 819 ⟶ 1,239:
end program twosum
</syntaxhighlight>
{{out}}
Line 825 ⟶ 1,245:
=={{header|FreeBASIC}}==
<
' "a" is the array of sorted non-negative integers
Line 865 ⟶ 1,285:
Print
Print "Press any number to quit"
Sleep</
{{out}}
Line 874 ⟶ 1,294:
=={{header|Go}}==
{{trans|Kotlin}}
<
import "fmt"
Line 910 ⟶ 1,330:
fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum)
}
}</
{{out}}
Line 919 ⟶ 1,339:
=={{header|Haskell}}==
====Returning first match====
<
twoSum num list = sol ls (reverse ls)
where
Line 933 ⟶ 1,353:
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs
main = print $ twoSum 21 [0, 2, 11, 19, 90]</
{{out}}
<pre>[1,3]</pre>
Line 940 ⟶ 1,360:
Listing multiple solutions (as zero-based indices) where they exist:
<
sumTo n ns =
let ixs = zip [0 ..] ns
Line 953 ⟶ 1,373:
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 n ns =
let ixs = zip [0 ..] ns
Line 965 ⟶ 1,385:
main :: IO ()
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]</
{{Out}}
<pre>(1,3)
Line 976 ⟶ 1,396:
<tt>fullimag</tt> library used to pretty print lists.
<
# twosum.icn, find two array elements that add up to a given sum
# Dedicated to the public domain
Line 1,006 ⟶ 1,426:
}
return []
end</
{{out}}
Line 1,018 ⟶ 1,438:
So, first off, our basic approach will be to find the sums:
<
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:
<
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:
<
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:
<
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:
<
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:
<
┌───┬───┐
│1 3│3 1│
Line 1,067 ⟶ 1,487:
└───┘
;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90
1 3</
Finally, let's start pulling our arguments out using that three verbs combining form:
<
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:
<
1 3</
And, let's finish the job, give this a name, and test it out:
<
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.)
Line 1,089 ⟶ 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.)
<
sums=. +/~ y
matches=. x = sums
Line 1,095 ⟶ 1,515:
pair_inds=. ($matches) #: sum_inds
; {. a: ,~ <"1 pair_inds
)</
And, testing:
<
1 3</
Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement:
<
sums=. +/~ y
matches=. x = sums
Line 1,114 ⟶ 1,534:
i.0
end.
)</
Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:
<
'''Alternative approach'''
Line 1,124 ⟶ 1,544:
An alternative method for identifying and returning non-duplicate indicies of the pairs follows.
<
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.
<
getIdx=: 4 $. $.
twosum_alt=: getIdx@zeroLowerTri@(= +/~)</
Testing ...
<
1 3</
=={{header|Java}}==
{{trans|Lua}}
<
public class TwoSum {
Line 1,163 ⟶ 1,583:
return null;
}
}</
<pre>[1, 3]</pre>
Line 1,177 ⟶ 1,597:
in the map result are eliminated by the concat.
<
var concatMap = function (f, xs) {
return [].concat.apply([], xs.map(f))
Line 1,192 ⟶ 1,612:
}(21, [0, 2, 11, 19, 90]);
})();
</syntaxhighlight>
{{Out}}
<syntaxhighlight lang
===ES6===
Line 1,201 ⟶ 1,621:
Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc.
{{Trans|Haskell}}
<
'use strict';
Line 1,251 ⟶ 1,671:
sumTwo(21, [0, 2, 11, 19, 90, 10])
);
})();</
{{Out}}
<pre>[[1,3],[2,5]]</pre>
Line 1,257 ⟶ 1,677:
=={{header|Jsish}}==
Based on Javascript entry.
<
function twoSum(target, list) {
var concatMap = function (f, xs) {
Line 1,278 ⟶ 1,698:
;twoSum(21, list);
;list[twoSum(21, list)[0][0]];
;list[twoSum(21, list)[0][1]];</
{{out}}
Line 1,291 ⟶ 1,711:
'''Works with gojq, the Go implementation of jq.
{{trans|Julia}}
<
. as $v
| {i: 0, j: ($v|length - 1) }
Line 1,302 ⟶ 1,722:
[0, 2, 11, 19, 90]
| (twosum(21), twosum(25))
</syntaxhighlight>
{{out}}
<pre>
Line 1,312 ⟶ 1,732:
{{works with|Julia|0.6}}
{{trans|Python}}
<
i = 1
j = length(v)
Line 1,327 ⟶ 1,747:
end
@show twosum([0, 2, 11, 19, 90], 21)</
{{out}}
Line 1,333 ⟶ 1,753:
=={{header|Kotlin}}==
<
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? {
Line 1,361 ⟶ 1,781:
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum")
}
}</
{{out}}
Line 1,369 ⟶ 1,789:
=={{header|Liberty BASIC}}==
<
myArray(1) = 2
myArray(2) = 11
Line 1,394 ⟶ 1,814:
Wend
twoToSum$ = "[]"
End Function</
{{out}}
<pre>[1,3]</pre>
Line 1,400 ⟶ 1,820:
=={{header|Lua}}==
Lua uses one-based indexing.
<
local i, j, s = 1, #numbers
while i < j do
Line 1,415 ⟶ 1,835:
end
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))</
{{out}}
<pre>2,4</pre>
=={{header|Maple}}==
<
local i,j,temp:
i,j := 1,numelems(arr):
Line 1,436 ⟶ 1,856:
end proc:
L := Array([0,2,2,11,19,19,90]);
two_sum(L, 21);</
{{Out|Output}}
Note that Maple does 1 based indexing.
Line 1,443 ⟶ 1,863:
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Block[{indices = Subsets[Range@Length@data, {2}]},
Cases[indices, _?(Total@data[[#]] == sum &)]]
twoSum[{0, 2, 11, 19, 90}, 21] // TableForm</
{{out}}<pre>
Line 1,455 ⟶ 1,875:
=={{header|MiniScript}}==
<
// 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.
Line 1,466 ⟶ 1,886:
end function
print twoSum([0, 2, 11, 19, 90], 21)</
Output:
Line 1,472 ⟶ 1,892:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,ReadChar;
Line 1,517 ⟶ 1,937:
WriteString(buf);
ReadChar;
END TwoSum.</
=={{header|Nim}}==
<
if src.len < 2:
return
Line 1,553 ⟶ 1,973:
main()</
=={{header|Objeck}}==
{{trans|Java}}
<
function : Main(args : String[]) ~ Nil {
sum := 21;
Line 1,599 ⟶ 2,019:
}
}
</syntaxhighlight>
Output:
Line 1,609 ⟶ 2,029:
{{trans|C}}
<
let n = Array.length numbers in
let res = ref [] in
Line 1,629 ⟶ 2,049:
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.
Line 1,640 ⟶ 2,060:
=={{header|ooRexx}}==
<
x=21
n=0
Line 1,652 ⟶ 2,072:
End
If n=0 Then
Say '[] - no items found' </
{{out}}
<pre>[0,1]
Line 1,659 ⟶ 2,079:
=={{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 ).
<
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
Line 1,774 ⟶ 2,194:
else
writeln('No solution found');
end.</
{{out}}
<pre>
Line 1,788 ⟶ 2,208:
=={{header|Perl}}==
{{trans|Python}}
<
use warnings;
use feature 'say';
Line 1,810 ⟶ 2,230:
@indices = two_sum(25, @numbers);
say join(', ', @indices) || 'No match';</
{{out}}
<pre>1, 3
Line 1,816 ⟶ 2,236:
=={{header|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;">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,828 ⟶ 2,248:
<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>
<!--</
{{trans|Raku}}
<!--<
<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>
Line 1,842 ⟶ 2,262:
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
{{Out}}
Phix uses 1-based indexes
Line 1,850 ⟶ 2,270:
=={{header|Phixmonti}}==
<
def two_sum /# arr num -- n #/
Line 1,871 ⟶ 2,291:
( 0 2 11 19 90 )
21 two_sum ?
25 two_sum ?</
{{out}}
<pre>[2, 19]
Line 1,879 ⟶ 2,299:
=={{header|PicoLisp}}==
<
(for ((I . A) Lst A (cdr A))
(T
Line 1,889 ⟶ 2,309:
(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) )</
{{out}}
<pre>(2 . 4) NIL (3 . 4)</pre>
Line 1,895 ⟶ 2,315:
=={{header|PowerShell}}==
Lazy, '''very''' lazy.
<syntaxhighlight lang="powershell">
$numbers = @(0, 2, 11, 19, 90)
$sum = 21
Line 1,921 ⟶ 2,341:
Expression = { @($_.FirstIndex, $_.SecondIndex) }
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,931 ⟶ 2,351:
=={{header|Python}}==
{{trans|Raku}}
<
i = 0
j = len(arr) - 1
Line 1,946 ⟶ 2,366:
numbers = [0, 2, 11, 19, 90]
print(two_sum(numbers, 21))
print(two_sum(numbers, 25))</
or, in terms of '''itertools.product''':
{{Works with|Python|3.7}}
<
from itertools import (product)
Line 2,034 ⟶ 2,454:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10]
Line 2,059 ⟶ 2,479:
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''':
{{Works with|Python|3.7}}
<
from itertools import chain
Line 2,110 ⟶ 2,530:
if __name__ == '__main__':
main()</
{{Out}}
<pre>[(1, 3), (2, 5)]
Line 2,121 ⟶ 2,541:
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.
<
[ -1 peek ] is last ( [ --> n )
Line 2,153 ⟶ 2,573:
' [ 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</
{{out}}
Line 2,163 ⟶ 2,583:
=={{header|Racket}}==
<
(define (two-sum v m)
(let inr ((l 0) (r (sub1 (vector-length v))))
Line 2,178 ⟶ 2,598:
(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)))</
=={{header|Raku}}==
Line 2,185 ⟶ 2,605:
===Procedural===
{{trans|zkl}}
<syntaxhighlight lang="raku"
die '@numbers is not sorted' unless [<=] @numbers;
Line 2,200 ⟶ 2,620:
say two_sum ( 0, 2, 11, 19, 90 ), 21;
say two_sum ( 0, 2, 11, 19, 90 ), 25;</
{{out}}
<pre>(1 3)
Line 2,208 ⟶ 2,628:
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).
<syntaxhighlight lang="raku"
# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique
(
Line 2,233 ⟶ 2,653:
say two-sum-rl(@a, $_);
say two-sum-lr(@a, $_);
}</
{{out}}
<pre>(1 3)
Line 2,242 ⟶ 2,662:
=={{header|REXX}}==
===version 1===
<
list='-5 26 0 2 11 19 90'
Do i=0 By 1 Until list=''
Line 2,262 ⟶ 2,682:
Say '[] - no items found'
Else
Say z 'solutions found'</
{{out}}
<pre>[0,1] -5 26 21
Line 2,282 ⟶ 2,702:
A little extra code was added to have the output columns aligned.
<
numeric digits 500 /*be able to handle some larger numbers*/
parse arg targ list /*obtain optional arguments from the CL*/
Line 2,305 ⟶ 2,725:
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. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,351 ⟶ 2,771:
=={{header|Ring}}==
<
# Project : Two Sum
Line 2,371 ⟶ 2,791:
next
next
</syntaxhighlight>
Output:
<pre>
Line 2,377 ⟶ 2,797:
target sum: 21
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>
=={{header|Ruby}}==
<
numbers.each_with_index do |x,i|
if j = numbers.index(sum - x) then return [i,j] end
Line 2,389 ⟶ 2,833:
numbers = [0, 2, 11, 19, 90]
p two_sum(numbers, 21)
p two_sum(numbers, 25)</
{{out}}
Line 2,398 ⟶ 2,842:
When the size of the Array is bigger, the following is more suitable.
<
numbers.each_with_index do |x,i|
key = sum - x
Line 2,406 ⟶ 2,850:
end
[]
end</
=={{header|Rust}}==
<
use std::ops::Add;
Line 2,439 ⟶ 2,883:
println!("{:?}", two_sum(&arr, sum));
}</
{{out}}
Line 2,447 ⟶ 2,891:
=={{header|Scala}}==
<
object TwoSum extends App {
Line 2,463 ⟶ 2,907:
}
}</
{{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}}==
{{trans|Raku}}
<
var (i, j) = (0, numbers.end)
while (i < j) {
Line 2,481 ⟶ 2,925:
say two_sum([0, 2, 11, 19, 90], 21)
say two_sum([0, 2, 11, 19, 90], 25)</
{{out}}
<pre>
Line 2,490 ⟶ 2,934:
=={{header|Stata}}==
Notice that array indexes start at 1 in Stata.
<
i = 1
j = length(a)
Line 2,505 ⟶ 2,949:
+---------+
1 | 2 4 |
+---------+</
=={{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}}==
<
int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0;
Line 2,522 ⟶ 2,976:
if (check == 0)
print("[]");
}</
{{out}}
<pre>[1,3]</pre>
=={{header|VBA}}==
<
Function two_sum(a As Variant, t As Integer) As Variant
Dim i, j As Integer
Line 2,554 ⟶ 3,008:
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</
{{out}}
<pre>
Line 2,566 ⟶ 3,020:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function TwoSum(numbers As Integer(), sum As Integer) As Integer()
Line 2,590 ⟶ 3,044:
End Sub
End Module</
{{out}}
<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}}==
{{trans|Python}}
{{works with|nasm}}
<
section .data
outputArr dd 0,0,0
Line 2,639 ⟶ 3,126:
mov eax, outputArr ;address of outputArr is returned in eax
ret
</syntaxhighlight>
=={{header|Wren}}==
<
var c = a.count
if (c < 2) return []
Line 2,665 ⟶ 3,152:
}
System.print()
}</
{{out}}
Line 2,680 ⟶ 3,167:
=={{header|XPL0}}==
Test cases from Algol 68.
<
int Size, Array, Sum, I, J;
[Text(0, "[");
Line 2,696 ⟶ 3,183:
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]
]</
{{out}}
Line 2,704 ⟶ 3,191:
[]
[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>
=={{header|zkl}}==
The sorted O(n) no external storage solution:
<
i,j:=0,ns.len()-1;
while(i<j){
Line 2,715 ⟶ 3,289:
else if(s>sum) j-=1;
}
}</
<
twoSum2(25,T(0,2,11,19,90)).println();</
{{out}}
<pre>
Line 2,724 ⟶ 3,298:
</pre>
The unsorted O(n!) all solutions solution:
<
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(25,T(0,2,11,19,90,21)).println();</
{{out}}
<pre>
|