Count Good Meals — Algorithms&Visualizations

Photo by Rachel Park

Introduction
Recently I’ve got to solve a problem on LeetCode, and decided to write this article because, even though it was not extremely hard, the whole complexity was in the precomputation of some data. Let’s have a look:

The Problem
As already mentioned, I came across this medium-difficulty problem while solving a coding challenge on LeetCode. The title is “Cout Good Meals”:

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i​​​​​​th​​​​​​​​ item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Constraints:
1 <= deliciousness.length <=10⁵
0 <= deliciousness[i] <= 2²⁰

Example:
Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

The First Approach
Before jumping into a more detailed analysis, some might be wondering how to solve just a piece of the whole challenge, which is: “How to figure out that a number is a power of two?”
Let’s consider two options:

1. Divide the number by 2 as long as the result is 1. If the result of the division is not an integer, the number is not a power of two:
   Example:
   Is 64 a power of two?
   64 / 2 = 32
   32 / 2 = 16
   16 / 2 = 8
   8 / 2 = 4
   4 / 2 = 2
   2 / 2 = 1 => TRUE
   Is 50 a power of two?
   50 / 2 = 25
   25 / 2 = 12.5 => FALSE (12.5 is not an integer)
2. We can precompute an array containing all the numbers that are power of two. If a number is not in the array, is not a power of two:
   [1, 2, 4, 8, 16, 32, 64, …]

Even if faster, the drawback of the second approach is that we can only precompute a finite quantity of power-of-two numbers, consequently if we happened to have a number, which is a power of two, but it’s bigger than the maximum element of our precomputed array, the result would be FALSE.
Ok, this is a big of a drawback, but take a glance at the constraints:
0≤deliciousness[i]≤ 2²⁰
This constraint tells us that we are not going to be handling numbers bigger than 2²⁰ and that our precomputed array containing power-of-two elements will be comprise only 20 elements! It sounds great, doesn’t it?

Let’s get back to the problem. At first sight, we might think of solving it by picking one element at a time, and then iterate over the rest of the elements ahead, counting the good meals:
Input: deliciousness = [1,1,0,15,5,4,4]
Output: 8

Please, note that we have to iterate only over the elements sitting after the one that we are considering. As a matter of fact, the couples (avocado, egg) and (egg, avocado) are identical, meaning that they should count as 1!

This approach seems to work, nevertheless, we are not going to be following this path. Why? Once again, take a look at the constraints. The input array might comprise up to 10⁵ elements, and an algorithm with O(n²) time complexity doesn’t have a snowball’s chance in hell of coming up with a solution before running out of time.

The Second Approach
We have already seen that picking one element and going over all the successive ones is a correct solution, but too slow in terms of time complexity.
This is a great opportunity to abstract the problem and come up woth a general solution for these kinds of problems that can always come in handy.
What we are asked to do is picking every couple of elements and checking for a specific condition (if two ingredients make a good meal).

Every time we select an element, we should be wondering:

a) “What is the element that we are looking for to satisfy the condition?”, or in other words, given a specific food, what other one do I need to make a good meal?
(Example: given a food whose deliciousness is 10, we need to find another food whose deliciousness is 6 or 22 or …)

b) “Once defined the element I am searching for, how many of these elements I have seen?”.
(Example: I’m considering a food whose deliciousness is 10, and I know that I have two elements with deliciousness 6 and another one with deliciousness 22, then I can conclude that I can create 3 good meals: (10+6), (10+6), (10+22))

Let’s try to visualize it:

At each step, an ingredient gets picked.
If I look among the already visited ingredients, will I find some pairs to make a good meal?
If the answer is yes, I’ll be counting the pairs, otherwise, I can move forward.
Example: When I analyze the tomatoe, I have already visited the avocado and the egg, so I can pair these ingredients.

Wait a minute, this solution is absolutely not different from the first approach! Right, we are still picking one element at a time and going backward to find the ingredients we need to make good meals. Unfortunately, we haven’t reduced the time complexity.

The Third approach
After two failing attempts, it should be clear that the problem is that for every ingredient, we potentially need to iterate over all the others. This makes the algorithm complexity explode.

In other words, when we respond to the question (a) “What is the element that we are looking for to satisfy the condition?”, instead of replying with a single element, we respond with a set.
In other words, given an ingredient with deliciousness 5, the response to the question (a) would be all the ingredients with deliciousness 3, but also 11, but also 27, and so on.
We definitely need to put in place some extra conditions that reduce the elements in the response to the question (a) down to a limited and well-defined number of ingredients. As a matter of fact, if we could reply: “Given an ingredient with deliciousness 5, I need to look for the ingredients with deliciousness 3” that would definitely speed the search up, correct? But how? Let’s proceed by attempts:

Let’s see what happens if, for each ingredient, we just look for the ingredients whose deliciousness would help reach just the closest power-of-two number. For instance, given an ingredient with deliciousness 6, we will just look for the ingredient with deliciousness 2 because 6+2=8 and 8 is the closest power-of-two number to 6:

When we pick the egg, its deliciousness is 1, which is already a power-of-two, meaning that we will be looking for an ingredient with deliciousness = 0, which we haven’t seen at this point.
The same is for the onion, its deliciousness is 4, so we will be searching for an ingredient whose deliciousness equals 0. At this point, we have already seen the wine, but we are missing out on the pair (onion, beer).

In the picture, the red arrows represent all the couples that, not surprisingly, we are missing out. At this point, we could claim that we could fix the problem if given an ingredient whose deliciousness is already a power of two, other then looking for ingredients with 0 deliciousness, we also search for those with the same deliciousness value.

Well, that’s true, we would definitely find the correct solution for the above example, but let me change the input just a little bit:
Input: deliciousness = [1,1,0,15,12,4,4]
Output: 10

We have sorted one problem out by looking for both zero-deliciousness ingredients and same deliciousness ingredients when the considered food’s deliciousness is already a power-of-two number.
Example: When we consider the onion, its deliciousness is 4, which is a power-of-two number (2²), consequently we will be looking for ingredients with deliciousness 0 and 4.

However, we are still missing out on some couples, like the onions (deliciousness 4) and the yellow bell pepper(deliciousness 12).

I feel like we are close to the correct solution, just an extra effort. What can we do? If it wasn’t clear yet, take some time to analyze the image a bit longer.

If you have figured it out, you can jump to the code section, otherwise no worries, I’ll be explaining it to you straight away.
As we mentioned, given an ingredient, we want to find the other that make the total deliciousness equal to the closest power-of-two number. It means that when we analyze the onion or the beer (deliciousness=4), we look for ingredients with deliciousness=4 (or 0 because 4 is already a power-of-two itself). And when we analyze the bell pepper (deliciousness=12)? Well, we look for other ingredients to reach deliciousness=16, meaning ingredients with deliciousness equal to 4.
Still not clear? Let me rephrase that:
For deliciousness=4, we look for deliciousness=4 (and deliciousness=0)
For deliciousness=12, we look for deliciousness=4

So in other words, when we consider food with deliciousness=12, we need to have all the ingredients with deliciousness=4 in front of us, otherwise, we will be missing out o some good meals.

So apparently we just need to sort the array!

Some might be wondering what assures that, given an ingredient deliciousness, we can reach the closest power-of-two number only adding up smaller deliciousnesses and not bigger ones? In that case, sorting the array wouldn’t help out! Let’s eradicate this last doubts with an image that speaks louder than words:

As we can see from the image, each power-of-two number is twice the previous one (obviously, otherwise it wouldn’t be a power of two!). In other words, whatever deliciousness we are considering, the closest reachable power-of-two number cannot be further than the delicious itself.
For example, given a deliciousness of 5, the only deliciousness that added up can help reach 8 is 3.

We are 100% sure that adding up a number greater or equal to the deliciousness itself will give a number bigger than the power-of-two number that we are trying to reach. The only exceptions are the already power-of-two numbers, which can reach the closest power-of-two element by adding zero or equal deliciousness.
For example, given a deliciousness of 16, the only deliciousness that added up can help reach 32 is 16, but also deliciousnesses equal to 0 give a power-of-two number, 16 itself.

The Code

Conclusions

I hope you enjoyed this article and learned something new. I can’t wait to read your feedback.
For other challenge solutions, don’t hesitate to visit my profile. Have a great day!

“Live as if you were to die tomorrow. Learn as if you were to live forever.” — Mahatma Gandhi