Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple like so: (index1, index2)
.
For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.
The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).
Based on: https://leetcode.com/problems/two-sum/
twoSum [1, 2, 3] 4 === (0, 2)
Thank you to wthit56 and 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!
Top comments (18)
Haskell
A recursive solution that checks for each item
x
in the list if there is an item in the rest of the list that, added tox
, results in the target value.The input will always be valid that's even worst than premature optimizations.
However, for the purpose of this challenge, I'll take that assumption, because while super important, input validation is boring.
My answer inspired by willsmart's answer.
C#, with comments on every line, so that everyone can understand it even if they don't speak the language:
The simple, O(n2) solution - using a nested loop.
The sophisticated, O(n) solution - using a single loop and a helper hash map.
Try it online
Inspired by Michael Kohl's solution in F# (O(n) rules!), I did the same thing in Rust. All the credit to him :)
Another one
In Python, written with a O(n) solution with the given assumptions using a dictionary and enumeration to generate an index.
Haskell:
I know the question said the input is always good, but I didn't want to ignore possible errors in when using the function...
I'm not sure of the speed of this code either. My guess is it only evaluates combinations until it finds a correct one? But I'm not an expert on lazy evaluation and I'm pretty sure this could be faster.
JavaScript
Recursive solution.
Try it online.
reduce
is good for this one.Here's a JS quickie with O(n) complexity.
The
partials
map maps the index of each value to the value required to bring it up to the target. This can then be picked up by a later value to the get the answer.Perl solution. Walk the array, for each element, store the expected counterpart into a hash. If the element already exists in the hash, we have the pair.
Here is the Python solution: