Given a list of integers, find the two items that sum to 2020.
-
Naive approach: Naively going through the items one-by-one will give you n^n-1 solution space
-
Slightly cleverer: The maximum amount of naive we should ever need is 1010. We could built a list of pairs
(n, 2020-n)
wheren = 0...1010
. Then iterate over that list and find the items. By sorting the list and using binary search, we can get an average lookup of O(log n) per item. -
Possibly interesting: If we search the list, then recursively take the tail and head and compare them, we should be able to find a combination that works;
Given:
find: x + y === 40 [ 20, 3, 26, 7, 22, 37, 34, 38, 20, 31, 35, 0, 11, 33, 4, 26, 23, 28, 1, 4, 27, 26, 33, 5, 11, 27, 8, 32, 6, 26, 9, 35, 39, 14, 12, 38, 9, 5, 37, 28 ] sort it: [ 0, 1, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 11, 11, 12, 14, 20, 20, 22, 23, 26, 26, 26, 26, 27, 27, 28, 28, 31, 32, 33, 33, 34, 35, 35, 37, 37, 38, 38, 39 ]
Then we'll make a function that takes the head and tail, compares it; -> We need to keep the last head and tail of the list -> [head, xs, tail], (lastHead, lastTail) -> if is under, we'll recursively call the function with the rest -> if it's perfect, we'll return the comparison -> if it is over, we'll have to recurse left and right a bit (probably not far) to get the items
I might be overthinking this... We could also just go through the list and keep a list of the values we've seen subtracted from 2020. Then simply check when we encounter one of the ones we've already seen... This works...
So now we need to go deeper. My initial idea would be to simple deepen the recursion. Given our current function, if we multiply and the multiplication is less than 2020, instead of going to the next item, we should search the rest of the items to see if we can find something to make it to 2020 total. So not really deepening the recursion. Just add another function.
There are 200 items.
While this could be solved with some nested for loops. This might be easier / quicker with a combination of my earlier idea;
While incoherent, my initial idea of working with the sorted list was actually what we would want to do. If we're under 2020, you can call with the tail
, if were over, you can call with init
, slowly creeping towards the actuall 2020. Given the following example, that would reduce down to:
find: x + y + z === 210
tail == take everything but first
init == take everything but last
[
93, 134, 14, 169, 101, 2, 80, 64, 35,
165, 131, 167, 198, 19, 199, 196, 126, 47,
76, 103, 192, 150, 102, 121, 2, 99, 177,
27, 195, 123, 104, 171, 169, 153, 97, 83,
133, 59, 158, 78
]
sort it:
[
2, 2, 14, 19, 27, 35, 47, 59, 64,
76, 78, 80, 83, 93, 97, 99, 101, 102,
103, 104, 121, 123, 126, 131, 133, 134, 150,
153, 158, 165, 167, 169, 169, 171, 177, 192,
195, 196, 198, 199
]
1: head == 2 ; tail == 199 -> 201 (too small, init)
2: head == 2 ; tail == 199 -> 201 (too small, init)
3: head == 14 ; tail == 199 -> 213 (too big, tail)
4: head == 14 ; tail == 198 -> 212 (too big, tail)
5: head == 14 ; tail == 196 -> 210 (spot on)
```
## Addendum
As pointed out by a redditor, `last` on a list is actually O(n) since lists are singly linked with no random access. So while a good effort / idea, the implementation / using lists actually mad the performance quite bad. Someone suggested using Sequence or Array to do it instead. I've rewritten the examples to do so (or well, copy pasted and adapted). There were others that used list comprehensions to solve this. The syntax there was not directly obvious to me, and it seems that it simply tries every combination (which is not the most performant option). All-in-all. I quite like this solution.