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];
}

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];
}