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!

Posted on Dec 22, 2019 by:

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

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

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

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

Discussion

Scala

Read next

How to Choose a Right JavaScript Framework for your Project?

How to choose the best CRM software?

FREE Cloud-Native Associate Certification (ACA)

How AI and IoT can transform the logistics and transportation management ecosystem?

dev.to staff

Scala

Read next

How to Choose a Right JavaScript Framework for your Project?

How to choose the best CRM software?

FREE Cloud-Native Associate Certification (ACA)

How AI and IoT can transform the logistics and transportation management ecosystem?

Log in to continue