Two sum: Difference between revisions

{{trans|Python}}

V i = 0

V j = arr.len - 1

V numbers = [0, 2, 11, 19, 90]

print(two_sum(numbers, 21))

{{out}}

=={{header|Action!}}==

INT i

Test(a,5,22)

Test(b,11,21)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Two_sum.png Screenshot from Atari 8-bit computer]

=={{header|Aime}}==

index x;

list l;

break;

}

{{Out}}

<pre>1 3</pre>

=={{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;

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 [] #

{{out}}

<pre>

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

{{out}}

<pre>

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)]

end repeat

return lst

{{Out}}

----

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

twoSum({0, 2, 11, 19, 90}, 21) -- Task-specified list.

twoSum({0, 3, 11, 19, 90}, 21) -- No matches.

{{output}}

{}

=={{header|Arturo}}==

loop.with:'i numbers 'x [

if not? null? j: <= index numbers s-x ->

print ["twoSum 21:" twoSum nums 21]

{{out}}

=={{header|AutoHotkey}}==

i := 1, j := a.MaxIndex()

while(i < j){

}

return "not found"

Outputs:<pre>2,4</pre>

=={{header|AWK}}==

# syntax: GAWK -f TWO_SUM.AWK

BEGIN {

return("[]")

}

{{out}}

<pre>

=={{header|Befunge}}==

>&:0\`#v_00g:1+00p6p

v >$&50p110p020p

>:#,_@ 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>

=={{header|C}}==

#include<stdio.h>

return 0;

}

Output :

<pre>

=={{header|C sharp|C#}}==

using System.Collections.Generic;

}

}

{{out}}

<pre>1, 3</pre>

=={{header|C++}}==

{{trans|C#}}

#include <map>

#include <tuple>

return 0;

{{out}}

<pre>{1,3}</pre>

=={{header|D}}==

void main() {

return [];

{{out}}

<pre>[1, 3]</pre>

=={{header|Dart}}==

main() {

var a = [1,2,3,4,5];

=={{header|Delphi}}==

{{libheader| System.SysUtils}}

{{libheader| System.Generics.Collections}}

{{Trans|Python}}

program Two_Sum;

Writeln('(', i, ',', j, ')');

Readln;

{{out}}

<pre>

</pre>

=={{header|Elixir}}==

def two_sum(numbers, sum) do

Enum.with_index(numbers) |>

numbers = [0, 2, 11, 19, 90]

IO.inspect RC.two_sum(numbers, 21)

{{out}}

=={{header|F_Sharp|F#}}==

// Two Sum : Nigel Galloway December 5th., 2017

let fN n i =

fN n 0

printfn "%A" (fN [0; 2; 11; 19; 90] 21)

{{out}}

<pre>

=={{header|Factor}}==

IN: rosetta-code.two-sum

x y = { } { x y } ? ;

{{out}}

<pre>

=={{header|Forth}}==

{{works with|Gforth|0.7.3}}

: A[] ( n -- A[n]) CELLS A @ + @ ;

:NONAME 1- ;

TEST1 3 TWOSUM CR

TEST1 8 TWOSUM CR

{{out}}

<pre>[1, 3]

=={{header|Fortran}}==

implicit none

end program twosum

{{out}}

=={{header|FreeBASIC}}==

' "a" is the array of sorted non-negative integers

Print

Print "Press any number to quit"

{{out}}

=={{header|Go}}==

{{trans|Kotlin}}

import "fmt"

fmt.Println("The numbers with indices", p1, "and", p2, "sum to", targetSum)

}

{{out}}

=={{header|Haskell}}==

====Returning first match====

twoSum num list = sol ls (reverse ls)

where

| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs

{{out}}

<pre>[1,3]</pre>

Listing multiple solutions (as zero-based indices) where they exist:

sumTo n ns =

let ixs = zip [0 ..] ns

main :: IO ()

Or, resugaring a little – pulling more into the scope of the list comprehension:

sumTo n ns =

let ixs = zip [0 ..] ns

main :: IO ()

{{Out}}

<pre>(1,3)

<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

}

return []

{{out}}

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

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

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

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

Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them:

1 3

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│

└───┘

;{.a:,~($ <@#: I.@,)21=+/~0 2 11 19 90

Finally, let's start pulling our arguments out using that three verbs combining form:

1 3

;{.a:,~21 ($ <@#: I.@,)@([ = +/~@])0 2 11 19 90

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:

And, let's finish the job, give this a name, and test it out:

21 twosum 0 2 11 19 90

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.)

sums=. +/~ y

matches=. x = sums

pair_inds=. ($matches) #: sum_inds

; {. a: ,~ <"1 pair_inds

And, testing:

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

i.0

end.

Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:

'''Alternative approach'''

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

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 $. $.

Testing ...

=={{header|Java}}==

{{trans|Lua}}

public class TwoSum {

return null;

}

<pre>[1, 3]</pre>

in the map result are eliminated by the concat.

var concatMap = function (f, xs) {

return [].concat.apply([], xs.map(f))

}(21, [0, 2, 11, 19, 90]);

})();

{{Out}}

===ES6===

Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc.

{{Trans|Haskell}}

'use strict';

sumTwo(21, [0, 2, 11, 19, 90, 10])

);

{{Out}}

<pre>[[1,3],[2,5]]</pre>

=={{header|Jsish}}==

Based on Javascript entry.

function twoSum(target, list) {

var concatMap = function (f, xs) {

;twoSum(21, list);

;list[twoSum(21, list)[0][0]];

{{out}}

'''Works with gojq, the Go implementation of jq.

{{trans|Julia}}

. as $v

| {i: 0, j: ($v|length - 1) }

[0, 2, 11, 19, 90]

| (twosum(21), twosum(25))

{{out}}

<pre>

{{works with|Julia|0.6}}

{{trans|Python}}

i = 1

j = length(v)

end

{{out}}

=={{header|Kotlin}}==

fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? {

println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum")

}

{{out}}

=={{header|Liberty BASIC}}==

myArray(1) = 2

myArray(2) = 11

Wend

twoToSum$ = "[]"

{{out}}

<pre>[1,3]</pre>

=={{header|Lua}}==

Lua uses one-based indexing.

local i, j, s = 1, #numbers

while i < j do

end

{{out}}

<pre>2,4</pre>

=={{header|Maple}}==

local i,j,temp:

i,j := 1,numelems(arr):

end proc:

L := Array([0,2,2,11,19,19,90]);

{{Out|Output}}

Note that Maple does 1 based indexing.

</pre>

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Block[{indices = Subsets[Range@Length@data, {2}]},

Cases[indices, _?(Total@data[[#]] == sum &)]]

{{out}}<pre>

=={{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.

end function

Output:

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,ReadChar;

WriteString(buf);

ReadChar;

=={{header|Nim}}==

if src.len < 2:

return

=={{header|Objeck}}==

{{trans|Java}}

function : Main(args : String[]) ~ Nil {

sum := 21;

}

}

Output:

{{trans|C}}

let n = Array.length numbers in

let res = ref [] in

List.iter (fun (i, j) ->

Printf.printf "# Found: %d %d\n" i j

Will return all possible sums, not just the first one found.

=={{header|ooRexx}}==

x=21

n=0

End

If n=0 Then

{{out}}

<pre>[0,1]

=={{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

else

writeln('No solution found');

{{out}}

<pre>

=={{header|Perl}}==

{{trans|Python}}

use warnings;

use feature 'say';

@indices = two_sum(25, @numbers);

{{out}}

<pre>1, 3

=={{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>

<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>

<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

=={{header|Phixmonti}}==

def two_sum /# arr num -- n #/

( 0 2 11 19 90 )

21 two_sum ?

{{out}}

<pre>[2, 19]

=={{header|PicoLisp}}==

(for ((I . A) Lst A (cdr A))

(T

(twosum (0 2 11 19 90) 21)

(twosum (-3 -2 0 1 5 8 11) 17)

{{out}}

<pre>(2 . 4) NIL (3 . 4)</pre>

=={{header|PowerShell}}==

Lazy, '''very''' lazy.

$numbers = @(0, 2, 11, 19, 90)

$sum = 21

Expression = { @($_.FirstIndex, $_.SecondIndex) }

}

{{out}}

<pre>

=={{header|Python}}==

{{trans|Raku}}

i = 0

j = len(arr) - 1

numbers = [0, 2, 11, 19, 90]

print(two_sum(numbers, 21))

or, in terms of '''itertools.product''':

{{Works with|Python|3.7}}

from itertools import (product)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>The indices of any two integers drawn from [0, 2, 11, 19, 90, 10]

or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''':

{{Works with|Python|3.7}}

from itertools import chain

if __name__ == '__main__':

{{Out}}

<pre>[(1, 3), (2, 5)]

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 )

' [ 0 2 11 19 20 ] 21 task echo cr

' [ 0 2 11 19 20 ] 25 task echo cr

{{out}}

=={{header|Racket}}==

(define (two-sum v m)

(let inr ((l 0) (r (sub1 (vector-length v))))

(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)

=={{header|Raku}}==

===Procedural===

{{trans|zkl}}

die '@numbers is not sorted' unless [<=] @numbers;

say two_sum ( 0, 2, 11, 19, 90 ), 21;

{{out}}

<pre>(1 3)

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).

# (((^@a X ^@a) Z=> (@a X+ @a)).grep($sum == *.value)>>.keys.map:{ .split(' ').sort.join(' ')}).unique

(

say two-sum-rl(@a, $_);

say two-sum-lr(@a, $_);

{{out}}

<pre>(1 3)

=={{header|REXX}}==

===version 1===

list='-5 26 0 2 11 19 90'

Do i=0 By 1 Until list=''

Say '[] - no items found'

Else

{{out}}

<pre>[0,1] -5 26 21

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*/

say

if sol==0 then sol= 'None' /*prettify the number of solutions if 0*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ring}}==

# Project : Two Sum

next

next

Output:

<pre>

=={{header|Ruby}}==

numbers.each_with_index do |x,i|

if j = numbers.index(sum - x) then return [i,j] end

numbers = [0, 2, 11, 19, 90]

p two_sum(numbers, 21)

{{out}}

When the size of the Array is bigger, the following is more suitable.

numbers.each_with_index do |x,i|

key = sum - x

end

[]

=={{header|Rust}}==

use std::ops::Add;

println!("{:?}", two_sum(&arr, sum));

{{out}}

=={{header|Scala}}==

object TwoSum extends App {

}

{{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) {

say two_sum([0, 2, 11, 19, 90], 21)

{{out}}

<pre>

=={{header|Stata}}==

Notice that array indexes start at 1 in Stata.

i = 1

j = length(a)

+---------+

1 | 2 4 |

=={{header|Vala}}==

int arr[] = { 0, 2, 11, 19, 90 }, sum = 21, i, j, check = 0;

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

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))

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Function TwoSum(numbers As Integer(), sum As Integer) As Integer()

End Sub

{{out}}

<pre>1, 3</pre>

=={{header|Vlang}}==

{{trans|Go}}

len := a.len

if len < 2 {

println("The numbers with indices $p1 and $p2 sum to $target_sum")

}

{{out}}

{{trans|Python}}

{{works with|nasm}}

section .data

outputArr dd 0,0,0

mov eax, outputArr ;address of outputArr is returned in eax

ret

=={{header|Wren}}==

var c = a.count

if (c < 2) return []

}

System.print()

{{out}}

=={{header|XPL0}}==

Test cases from Algol 68.

int Size, Array, Sum, I, J;

[Text(0, "[");

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}}

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

// by Galileo, 04/2022

Else

Print "The numbers with indices ", b(1), " and ", b(2), " sum to ", targetSum

{{out}}

<pre>The numbers with indices 2 and 4 sum to 21

=={{header|zkl}}==

The sorted O(n) no external storage solution:

i,j:=0,ns.len()-1;

while(i<j){

else if(s>sum) j-=1;

}

{{out}}

<pre>

</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)) })

{{out}}

<pre>