Count Good Meals - Leetcode Solution

Problem Statement: 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 ith item of food. You can select any subset of the given items to make a good meal.

Return the number of different good meals you can make from different subsets of deliciousness.

Since the answer may be too large, return it modulo 10^9 + 7.

Solution Approach:

• Define the maximum deliciousness of a meal to be 2^20, since 2^20 + 2^20 > 2^31-1 (the maximum value for "sum")
• Iterate through each pairs of foods i, j and check if the sum is a power of two between 2 and max deliciousness
• Store all possible sums of foods that work in a dictionary
• Iterate through the deliciousness array and check for pairs of foods in the dictionary that add up to the current deliciousness
• Keep track of the total number of good meals found

Python3 Solution:

class Solution: def countPairs(self, deliciousness: List[int]) -> int: MOD = 109 + 7 MAX_DELICIOUSNESS = 220

    power_of_two = set([2**i for i in range(22)])
    delicious_dict = defaultdict(int)

    n = len(deliciousness)
    ans = 0

    for i in range(n):
        for j in range(i+1, n):
            food_sum = deliciousness[i] + deliciousness[j]
            if food_sum in power_of_two and food_sum <= MAX_DELICIOUSNESS:
                ans += delicious_dict[food_sum] % MOD

        delicious_dict[deliciousness[i]] += 1

    return ans % MOD

1