Daily Challenge #141 - Two Sum

dev.to staff Dec 22 '19 ・1 min read

#challenge

Daily Challenge (245 Part Series)

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!

Daily Challenge (245 Part Series)

DISCUSS (10)

dev.to/you

Claim your page on DEV before someone else does

Join DEV Now

Open source

Free forever

Level up every day

🤝

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

You’re more than welcome to provide an alternative.

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

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

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

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

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

Sam

Jan 17

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]

code of conduct - report abuse

Daily Challenge #141 - Two Sum

dev.to staff Dec 22 '19 ・1 min read

dev.to/you

Claim your page on DEV before someone else does

Join DEV Now

dev.to staff

Scala

You're not worth hiring unless...

Daily Coding Challenge #17

Wing-Kam - May 30

What’s your alternative solution? Challenge #53

Adrian - May 29

6-10PM challenge problem #005

akbhairwal - Jun 1

List of Opensource Internships And Fellowships

Deepanshu Udhwani - May 29

dev.to/you

Claim your page on DEV before someone else does

Join DEV Now

dev.to staff

Scala

You're not worth hiring unless...

Daily Coding Challenge #17

Wing-Kam - May 30

What’s your alternative solution? Challenge #53

Adrian - May 29

6-10PM challenge problem #005

akbhairwal - Jun 1

List of Opensource Internships And Fellowships

Deepanshu Udhwani - May 29

Join our DEV Community :)