Two sum: Difference between revisions

 

;Task

 

 

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

 

=={{header|AppleScript}}==

{{Trans|JavaScript}}

{{Trans|Haskell}}

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.

 

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

end |λ|

end script

|>>=|(drop(i + 1, ixs), jIndices)

end |λ|

end script

|>>=|(ixs, ijIndices)

on run

end run

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

end |λ|

end script

if length of xs > 0 and class of (item 1 of xs) is string then

set empty to ""

foldl(append, empty, xs)

end concat

-- drop :: Int -> a -> a

on drop(n, a)

end if

end drop

-- enumFromTo :: Int -> Int -> [Int]

on enumFromTo(m, n)

return lst

end enumFromTo

-- foldl :: (a -> b -> a) -> a -> [b] -> a

on foldl(f, startValue, xs)

end tell

end foldl

-- length :: [a] -> Int

on |length|(xs)

length of xs

end |length|

-- map :: (a -> b) -> [a] -> [b]

on map(f, xs)

end tell

end map

-- min :: Ord a => a -> a -> a

on min(x, y)

end if

end min

-- Lift 2nd class handler function into 1st class script wrapper

-- mReturn :: Handler -> Script

end if

end mReturn

-- zip :: [a] -> [b] -> [(a, b)]

on zip(xs, ys)

end repeat

return lst

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

</pre>

 

 

#include<stdio.h>

 

return 0;

}

Output :

<pre>

[1,3]

</pre>

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

{

{

}

{{out}}

 

=={{header|Dart}}==

main() {

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

 

 

 

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

[1; 3]

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

[0, 6]

[2, 5]</pre>

 

=={{header|FreeBASIC}}==

 

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

Print

Print "Press any number to quit"

 

{{out}}

The numbers with indices 1 and 3 sum to 21

</pre>

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

 

=={{header|JavaScript}}==

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

if src.len < 2:

return

 

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

result[0] = base

result[1] = ext

 

 

 

=={{header|ooRexx}}==

x=21

do i=1 To a~items

Do j=i+1 To a~items

End

End

End

{{out}}

 

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

sub two_sum{

my $i = 0;

while ($i < $j) {

}

}

 

 

{{out}}

 

=={{header|Phix}}==

{{Out}}

Phix uses 1-based indexes

{2,4}

</pre>

 

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

i = 0

j = len(arr) - 1

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

print(two_sum(numbers, 21))

 

 

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

===version 1===

Do i=0 By 1 Until list=''

Parse Var list a.i list

End

x=21

Do j=i+1 To n

End

End

End

Else

{{out}}

 

===version 2===

 

Also, it's mentioned that the indices are zero─based, &nbsp; and formatted solutions are shown.

parse arg targ list /*obtain optional arguments from the CL*/

if targ='' | targ="," then targ= 21 /*Not specified? Then use the defaults*/

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

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

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

end /*b*/ /*show the 2 indices and the summation.*/

end /*a*/

say

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

<pre>

the target sum: 21

 

 

number of solutions found: 1

</pre>

<pre>

the target sum: 21

 

 

</pre>

 

=={{header|Ring}}==

# Project : Two Sum

 

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

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

var (i, j) = (0, numbers.end)

while (i < j) {

 

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

{{out}}

<pre>

[]

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

(2, 3)

 

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