Two sum: Difference between revisions

 

 

[http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum Stack Overflow: Find pair of numbers in array that add to given sum]

<br/><br/>

 

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

[]

[2, 3]

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

end twoSum

 

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

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

 

{{output}}

{}

 

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

(1,3)

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

{ 0 2 }

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

in [ (i, j)

| (i, x) <- ixs

, (x + y) == n ]

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

list[twoSum(21, list)[0][0]] ==> 2

list[twoSum(21, list)[0][1]] ==> 19</pre>

 

=={{header|Julia}}==

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

The numbers with indices 1 and 3 sum to 21

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

[2,5]

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

 

for base in 0 .. (src.len - 2):

result[0] = base

result[1] = ext

 

 

 

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

{{trans|Raku}}

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

[]</pre>

 

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

The list of numbers can be in any format, &nbsp; not just integers. &nbsp; Also, they need not be unique.

 

 

 

 

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 'the list: ' list /*echo the list to the terminal*/

say 'the target sum: ' targ /* " " target sum " " " */

do #=0 for words(list); _=word(list, #+1) /*examine the list, construct an array.*/

end /*#*/ /*W: the maximum width of any number. */

L= length(#) /*L: " " " " " index. */

say /* [↓] look for sum of 2 numbers=target*/

do a=0 for # /*scan up to the last number in array. */

sol= sol + 1 /*bump count of the number of solutions*/

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

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

<pre>

 

=={{header|Ring}}==

# Project : Two Sum

 

next

next

Output:

<pre>

target sum: 21

a solution: [1 3]

</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|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|X86 Assembly}}==

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

 

Indices: [0, 4] sum to 90 (0 + 90 = 90)

</pre>

 

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