loading...

Daily Challenge #141 - Two Sum

thepracticaldev profile image dev.to staff ・1 min read

Write a function that takes an array of integers and a target number.

The function should find two different integers in the array that give the target value when added together. Return the indices in a tuple [e.g. (index1, index2)]. Some tests will have multiple solutions.

Test Cases
[1234,5678,9012], 14690
[1,2,3], 4
[2,2,3], 4
[5,10,15,20,25,30], 50

Happy coding!


This challenge comes from wthit56 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
avalander profile image
Avalander

Scala

def solve (xs: Seq[Int], target: Int): Option[(Int, Int)] = {
  val indexed = xs zip (0 until xs.size)

  @tailrec
  def solveRec (xs: Seq[(Int, Int)]): Option[(Int, Int)] =
    xs match {
      case Nil            => None
      case (x, i) :: rest =>
        rest find {
          case (y, j) => x + y == target
        } match {
          case None         => solveRec(rest)
          case Some((y, j)) => Some((i, j))
        }
    }
  solveRec(indexed)
}

And the tests

class PairsumTest extends FunSuite {
  test("solve") {
    assert(solve(List(1234,5678,9012), 14690) == Some((1, 2)))
    assert(solve(List(1,2,3), 4) == Some((0, 2)))
    assert(solve(List(2,2,3), 4) == Some((0, 1)))
    assert(solve(List(5,10,15,20,25,30), 50) == Some((3, 5)))
    assert(solve(List(), 23) == None)
    assert(solve(List(5, 14, 38), 23) == None)
  }
}
Collapse
citizen428 profile image
Michael Kohl

Simple Ruby method chain:

def two_sum(a, target)
  a
    .each_with_index
    .to_a
    .combination(2)
    .inject([]) { |r, ((a, i1), (b, i2))| r << [i1, i2] if a + b == target ; r }
end

two_sum([1234,5678,9012], 14690) 
#=> [[1, 2]]

two_sum([5,10,15,20,25,30], 50)
#=> [[3,5]]

Note: it's generally preferable to use each_with_object instead of inject + explicitly returning r in the block, but this is just a coding challenge and it made the line fit within 80 characters 😉

Collapse
gdledsan profile image
Info Comment marked as low quality/non-constructive by the community. View code of conduct
Mundo

Ruby 😍
This one is ugly tho

Collapse
citizen428 profile image
Michael Kohl

You’re more than welcome to provide an alternative.

Collapse
erezwanderman profile image
erezwanderman

Javascript

// Corrected solution
const func = (arr, sum) =>
  arr
  .map((x, i) => [x, i])
  .map(([x1, i1], _, a) => [i1, a.findIndex(([x2, i2]) => i1 !== i2 && x1 + x2 === sum)])
  .find(([i1, i2]) => i2 !== -1);
Collapse
avalander profile image
Avalander

Doesn't this return the values that sum up to the target value and not their indices in the array?

Collapse
erezwanderman profile image
erezwanderman

It did. I've now corrected it, I hope.

Collapse
gdledsan profile image
Info Comment marked as low quality/non-constructive by the community. View code of conduct
Mundo

I can't believe thwre are people saying JS is beautiful

Collapse
idanarye profile image
Idan Arye

Rust:

fn two_sum(numbers: &[i64], target: i64) -> Option<(usize, usize)> {
    let mut complete_with = std::collections::HashMap::new();
    for (idx1, &num) in numbers.iter().enumerate() {
        if let Some(&idx2) = complete_with.get(&(target - num)) {
            return Some((idx1, idx2));
        } else {
            complete_with.insert(num, idx1);
        }
    }
    None
}

fn main() {
    for (numbers, target) in &[
        (vec![1234, 5678, 9012], 14690),
        (vec![1, 2, 3], 4),
        (vec![2, 2, 3], 4),
        (vec![5, 10, 15, 20, 25, 30], 50),
    ] {
        if let Some((idx1, idx2)) = two_sum(numbers, *target) {
            assert!(numbers[idx1] + numbers[idx2] == *target);
        }
    }
}

Collapse
gagandureja profile image
Gagan

python

from itertools import combinations
def idx_sum(lst,num):
    com=  list(combinations(lst,2)) # [(1, 5), (1, 2), (1, 4), (1, 6), (5, 2), (5, 4), (5, 6), (2, 4), (2, 6), (4, 6)]
    ans = [x for x in com if sum(x)==num]  # [(1, 5), (2, 4)]
    return [(lst.index(x),lst.index(y)) for x,y in ans]  # [(0, 1), (2, 3)]

print(idx_sum([1,5,2,4,6],6))
#[(0, 1), (2, 3)]

# defines result of the code

Collapse
mudlabs profile image
Sam

TypeScript

function twoSum(integers: number[], target: number): number[] {
    let index1: number = -1;
    let index2: number = -1;
    let solved: boolean = false;

    integers.map((integer1: number, index: number, array: number[]): void => {
        if (!solved) {
            const integer2 = ([...array])
                .filter((integer: number, _index: number) => _index !== index)
                .find(integer => integer1 + integer === target);

            if (integer2) {
                index1 = array.indexOf(integer1);
                index2 = array.lastIndexOf(integer2);
                solved = true;
            }
        }
        return;
    });

    return [index1, index2];
}

twoSum([1234, 5678, 9012], 14690); // [1, 2]
twoSum([1,2,3], 4); // [0, 2]
twoSum([2,2,3], 4); // [0, 1]
twoSum([5,10,15,20,25,30], 50); // [3, 5]