Originally Published on my blog
Day 01
part 01 ⭐
The first part of day one is a two-sum problem needs to get the
multiply of two entries that sum to 2020
The naive solution you can do two loops and make a condition whenever
the two numbers sum to 2020
break the loop and return the value.
function p1(input) {
for (let i = 0; i < input.length; i++)
for (let j = 0; j < input.length; j++)
if (input[i] + input[j] === 2020)
return input[i] * input[j];
}
This solution will take O(n^2)
time complexity for each element.
We can enhance our solution by using Map
data structure and only one loop
function p1(input) {
const map = new Map();
for (let i = 0; i < input.length; i++) {
const complement = 2020 - input[i];
if (map.has(complement))
return input[map.get(complement)] * input[i]
map.set(input[i], i);
}
}
this solution will take O(n)
time complexity by traverse the list containing
n
element only once.
part 02 ⭐
The difference in the part two that we need to get the multiply for
three
numbers that sum to 2020
We can use the same naive solution by using brute force with three loops.
function p2(input) {
for (let i = 0; i < input.length; i++)
for (let j = 0; j < input.length; j++)
for (let k = 0; k < input.length; k++)
if (input[i] + input[j] + input[k] === 2020)
return input[i] * input[j] * input[k];
}
Top comments (1)
Finished part 1. Yes, I initially thought of brute force. Then I figured to make 2 lists: lower half (gets all numbers less than half 2020) and upper half (gets the rest). The solution has to be a single number from each list.
Was pleased with myself. Then I read the instructions for part 2. Yuck. My list idea doesn't work.
I like your map solution to part 1.
But I have chosen to not read your part 2 post until I solve it myself.
Bruce