In this article, I’ll discuss on the Day – 1 problem of “Advent of Code”. And from today onwards, I will try to discuss everyday’s problem. Make sure you subscribe to the blog to stay in touch.
Feel free to share your ideas or even post your solutions in the comment section below.
Let’s start…
Table of Contents
PART – 1 of DAY – 1
The problem is simple – Given a list of years, you have to find the two entries that sum to 2020; And the output will be retrieved after multiplying those two years.
Test Input
1721
979
366
299
675
1456The very first thing that comes to the mind is Bruteforce approach.
Bruteforce Approach
In this approach, we loop over each and every combination of year in the list and check if their sum equals 2020. The solution is perfect and always works. But it is not so efficient.
The time complexity of this approach is O(n2).
Code for the same will be like this:
// APPROACH 1 - BRUTE FORCE
// Complexity - O(n2)
int bruteforce(int target) {
int len = input.size();
for (int i=0; i < len - 2; i++)
for (int j = i + 1; j < len - 1; j++)
if (input[i] + input[j] == target)
return input[i] * input[j];
return 0;
}This code will compare year in the list with every other year to check if their sum equals 2020. And if that condition is satisfied then multiplies both the numbers and returns the result.
Another approach to solve this is 2 pointer approach.
Two Pointer Approach
This approach is pretty awesome. This approach has a complexity of O(nlogn) which is a great improvement from the previous approach.
The nlogn comes from the fact that the array should be sorted. That is the prerequisite. This approach only works on the sorted array.
In this we start searching from the front and back simultaneously. We start by initializing the left pointer to the start of the array and right pointer to the end of the array. The with each iteration we compare the values at left pointer and right pointer. And if the sum equals 2020 then we return the multiplied result.
Let’s see the code:
// APPROACH 2 - PART 1
int two_pointer(int target) {
vector<int> input = {1721,979,366,299,675,1456};
sort(input.begin(), input.end());
int j = input.size() - 1;
for (int i = 0; i < input.size();)
if (input[i] + input[j] > target) j--;
else if (input[i] + input[j] < target) i++;
else return input[i] * input[j];
return 0;
}This is a pretty optimized solution and guarantees that the result will be retrieved in the O(nlogn) time.
Approach 3 – Maintain A Compliment Hash Set Of The Numbers
There is one more approach that makes use of the HashSet to store the compliment of the visited numbers. The Time Complexity of this approach is as follows:
- Time Complexity – O(n)
- Space Complexity – O(n)
Basically we trade space for time. Here’s the idea behind this approach.
Let’s say you have the following list.
vector<int> arr = {1721,979,366,299,675,1456};
Here we will iterate over each and every item in the list and check for its existence in the set. If it is not present in the set then we insert the compliment of that number to the set. So that the next time if we encounter any number which is already present in the set, we would immediately know that its compliments exist.
Let’s take a look at the code to understand the logic better.
// Approach 3 - Part - 1 | HashSet approach
int hash_set_approach(int target) {
unordered_set<int> complements;
vector<int> input = {1721,979,366,299,675,1456};
for (auto year: input) {
int complement = target - year;
if (complements.count(year) != 0)
return year * complement;
else
complements.insert(complement);
}
return 0;
}
As you can see in the above code. We go over each and every integer in the array and check its presence in the set. If the number is present we simply multiply the number with its complement to get the result.
But if the number is not present in the set then we take its complement and add to the set.
That way we keep a track of the numbers that we have seen before.
Great! you have seen all the three approaches with which the part one of the questions can be solved. Let’s take a look at part 2, shall we?
PART – 2 of DAY – 1
The problem is extended by adding one more requirement. That is, instead of finding the product from two numbers that sum up to 2020, you now have to find the product from three numbers that sums up to 2020.
Again, for solving the problem, you can expand the approach 1 – BruteForce approach which is the easiest but the time complexity now will be O(n^3). Or you can use approach 2- Three Pointer approach for which the time complexity will be O(n^2).
Approach 1 – Bruteforce
This is the fastest to impliment. You just have to insert one more loop for the third number.
// APPROACH 1 - BRUTE FORCE
// Complexity - O(n3)
int bruteforce(int target) {
int len = input.size();
for (int i=0; i < len - 2; i++)
for (int j = i + 1; j < len - 1; j++)
for (int k = j + 1; k < len; k++)
if (input[i] + input[j] + input[k] == target)
return input[i] * input[j] * input[k];
return 0;
}
Approach 2 – Three Pointer
This is the extension of the two pointer approach. We will be doing the same thing but with 3 pointers.
Here, the first step is to sort the given array O(nlogn) we will take 3 variables that will be used for finding the sum (let’s say i,j & k).
The variables j and k will behave just the same way they did in the two pointer approach. The new variable i will be responsible for the third number in the sum.
Since, the code will contain a nested loop, the overall complexity of this algorithm will be O(nlogn + n2) => O(n^2).
Let’s directly look at the code to understand how it works.
// APPROACH 2 - TWO POINTER
// Complexity - O(nlogn) + O(n2) = O(n2)
int three_pointer(int target) {
sort(input.begin(), input.end());
int len = input.size();
for(int i = 0; i < len - 2; i++)
for (int j = i + 1, k = len - 1; j < k;)
if (input[i] + input[j] + input[k] > target) k--;
else if (input[i] + input[j] + input[k] < target) j++;
else return input[i] * input[j] * input[k];
return 0;
}
These are the best ways I could come up with to solve the day one problem. Do share your comments and approach in the comments below.