Daily Challenge #141 - Two Sum

#challenge

dev.to staff Dec 22, 2019 ・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

Avalander • Dec 22 '19

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

Michael Kohl • Dec 23 '19

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 😉

Comment marked as low quality/non-constructive by the community. View code of conduct

Mundo • Dec 24 '19

Ruby 😍
This one is ugly tho

Michael Kohl • Dec 24 '19

You’re more than welcome to provide an alternative.

erezwanderman • Dec 22 '19

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

Avalander • Dec 22 '19

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

erezwanderman • Dec 22 '19

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

Comment marked as low quality/non-constructive by the community. View code of conduct

Mundo • Dec 24 '19

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

Idan Arye • Dec 22 '19

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

Gagan • Aug 20 '20

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

Sam • Jan 17 '20

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]

DEV Community

DEV Community is a community of 554,873 amazing developers

Daily Challenge #141 - Two Sum

Discussion

Scala

Read next

Weekly Coding Challenge - Week #10 - Clock

Fun With Linear Time: My Favorite Algorithm

AoC 2018 Day 5: Alchemical Reduction

Discover the Power of Closures in VueJS

DEV Community is a community of 554,873 amazing developers

Scala

Read next

Weekly Coding Challenge - Week #10 - Clock

Fun With Linear Time: My Favorite Algorithm

AoC 2018 Day 5: Alchemical Reduction

Discover the Power of Closures in VueJS

Log in to continue