DEV Community

Mahmoud Ashraf
Mahmoud Ashraf

Posted on • Originally published at mahmoudashraf.dev

Advent of Code 2020: Day 01

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];
}
Enter fullscreen mode Exit fullscreen mode

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
bruceberk profile image
BruceBerk

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