LeetCode 1711 - Count Good Meals

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to count the number of good meals that can be formed from a given list of food items. A good meal is defined as a pair of two different items whose combined deliciousness is a power of two. The input is an array of integers, deliciousness, where each element represents the deliciousness of a single food item. The output is the total number of such pairs modulo $10^9 + 7$.

The constraints indicate that the length of the array can be up to $10^5$ and each deliciousness value is between 0 and 220. These constraints are important because they tell us that a brute-force solution that checks every pair could be too slow for large arrays. The problem also clarifies that two items with the same deliciousness but different indices count as distinct items, which means we cannot skip duplicates.

Important edge cases include arrays with minimal size (1 or 2 elements), arrays with all identical elements, and arrays with zero deliciousness. The problem guarantees non-empty input but not necessarily unique values, so our solution must handle duplicates correctly.

Approaches

The brute-force approach would iterate over all possible pairs of items in the array, calculate their sum, and check whether it is a power of two. This approach is correct because it explicitly checks every possible combination, but it is too slow because it has $O(n^2)$ time complexity, which is prohibitive for $n = 10^5$.

The optimal approach uses a hash map to count occurrences of each deliciousness value while iterating through the array. For each item, we check all possible powers of two sums that could be formed with that item and look up how many times the complementary value (sum minus current value) has occurred so far. This reduces the time complexity to approximately $O(n \cdot \log C)$, where $C$ is the largest possible sum of two items (in this problem, at most $2^{22+1} = 2^{23}$), because there are only about 22 powers of two to check for each element. This approach uses extra space for the hash map, but it is efficient enough given the problem constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check all pairs, too slow for large n
Optimal	O(n * logC)	O(n)	Use hash map to count complements for powers of two

Algorithm Walkthrough

Initialize a hash map count_map to store the frequency of each deliciousness value encountered so far.
Initialize a variable result to zero to keep track of the number of good meals.
Precompute a list of powers of two up to the maximum possible sum. Since the maximum deliciousness[i] is 220, the largest possible sum is 440, but to be safe, consider powers of two up to $2^{22}$ or slightly higher.
Iterate through each value in the deliciousness array.
For each value, iterate through all precomputed powers of two power.
Calculate the complement needed = power - value.
If needed exists in the hash map, add count_map[needed] to result. This counts all valid pairs formed with value as the second element.
Increment count_map[value] to account for the current element for future iterations.
After processing all elements, return result % (10^9 + 7).

Why it works: For each element, we count all previously seen elements that can form a power-of-two sum with it. This ensures we count every valid pair exactly once and efficiently without checking every pair explicitly.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 10**9 + 7
        count_map = defaultdict(int)
        result = 0
        # Precompute powers of two up to 2^22 (enough for sums up to 2*2^20)
        powers_of_two = [1 << i for i in range(22)]
        
        for value in deliciousness:
            for power in powers_of_two:
                needed = power - value
                if needed in count_map:
                    result += count_map[needed]
            count_map[value] += 1
            
        return result % MOD

Implementation Explanation: We use a defaultdict to avoid key errors when checking if the complement exists. powers_of_two stores all sums that are valid powers of two. For each deliciousness value, we check against all powers of two, find the needed complement, and update the result. Finally, we increment the hash map to include the current value for future pairs.

Go Solution

func countPairs(deliciousness []int) int {
    const MOD int = 1e9 + 7
    countMap := make(map[int]int)
    result := 0
    powersOfTwo := make([]int, 22)
    
    for i := 0; i < 22; i++ {
        powersOfTwo[i] = 1 << i
    }
    
    for _, value := range deliciousness {
        for _, power := range powersOfTwo {
            needed := power - value
            if count, ok := countMap[needed]; ok {
                result = (result + count) % MOD
            }
        }
        countMap[value]++
    }
    
    return result
}

Go-specific Notes: Go requires explicit checks for map keys with ok. The modulo operation is applied incrementally to avoid integer overflow. The logic mirrors the Python version, with explicit array and map handling.

Worked Examples

Example 1: deliciousness = [1,3,5,7,9]

Iteration	value	count_map	Powers Checked	New Pairs Added	result
0	1	{}	1..2^21	0	0
1	3	{1:1}	1..2^21	(1,3)=4	1
2	5	{1:1,3:1}	1..2^21	(3,5)=8	2
3	7	{1:1,3:1,5:1}	1..2^21	(1,7)=8	3
4	9	{1:1,3:1,5:1,7:1}	1..2^21	(7,9)=16	4

Final result: 4

Example 2: deliciousness = [1,1,1,3,3,3,7]

value	count_map	Pairs Added	result
1	{}	0	0
1	{1:1}	(1,1)=2?	1
1	{1:2}	(1,1)=2?	3
3	{1:3}	(1,3)=3	6
3	{1:3,3:1}	(1,3)=3	9
3	{1:3,3:2}	(1,3)=3	12
7	{1:3,3:3}	(1,7)=3	15

Final result: 15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * logC)	For each element, we check about 22 powers of two; n is the array length
Space	O(n)	Hash map stores frequency of each distinct deliciousness value

The dominant factor is iterating through all elements and checking a constant number of powers of two for each element. The space is dominated by the hash map storing up to n elements.

Test Cases

# Basic examples
assert Solution().countPairs([1,3,5,7,9]) == 4  # Example 1
assert Solution().countPairs([1,1,1,3,3,3,7]) == 15  # Example 2

# Edge cases
assert Solution().countPairs([0]) == 0  # Single element
assert Solution().countPairs([0,0]) == 1  # Two zeros, sum = 0+0=0 not power of two
assert Solution().countPairs([1,2]) == 1  # Minimal valid pair
assert Solution().countPairs([1]*1000) == 0  # All identical elements, sum=2 not counted for powers >1
assert Solution().countPairs([2**20]*2) == 1  # Large numbers

Test	Why
[1,3,5,7,9]	Standard example, mix of sums forming powers of two
[