Leetcode 1711 - Count Good Meals

Link to Problem

Problem

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 $10^9 + 7$.

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

Approach

Another problem that is quite similar to Two Sum so we could know that we probably need to use an unordered_map. However, different from Two Sum, the target sum of two numbers is any number that is power of 2. And we are counting the possibile combinations, note that different indices are considered different.

Therefore, to solve this problem, we are using the unordered_map to store the current count of deliciousness[i]. And when iterated to another number that combined with deliciousness[i] is power of 2, we could know that the combinations available for the number equals to the count. Storing the current count prevents the algorithm from counting duplicates.

Solution

1. Setup a list of numbers that are power of 2, {$1, 2, 4, …, 2^{30}$} for checking if the num equals to any of the numbers later.
2. Iterate through deliciousness and check if there are number exist in hash map that combined with the number is power of 2. If there is, add the count of good meal with the count of num_power_of_2 - deliciousnedd[i] in the hast map.
3. Add one to the hash map of the iterated number.

Implementation

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        int count = 0;
        std::unordered_map<int, int> numCount;
        std::vector<int> powerList(31);

        for (int i = 0; i < 31; i++) {
            powerList[i] = 1 << i;
        }

        for (int i = 0; i < deliciousness.size(); i++) {
            
            for (auto p: powerList) {
                if (numCount.count(p - deliciousness[i])) {
                    count += numCount[p - deliciousness[i]];
                    count %= 1000000007;
                }
            }

            numCount[deliciousness[i]]++;
        }

        return count;
    }
};