Count Good Meals: Hash Map with Powers of Two

LeetCode 1711 asks you to count "good meals." You are given an array of integers called deliciousness, where each element represents the deliciousness of a meal ingredient. A good meal is a pair of ingredients whose deliciousness values sum to a power of 2. You need to return the total count of good meal pairs, modulo 10^9 + 7.

This is a classic complement-lookup problem with a twist. Instead of checking one target sum like Two Sum, you check against every relevant power of 2.

Why powers of two matter

At first glance, you might worry about checking an infinite number of powers of 2. But the constraints save you. Each deliciousness value is at most 2^20, so the maximum sum of any pair is 2^20 + 2^20 = 2^21. That means you only need to check 22 powers of 2, from 2^0 = 1 up to 2^21 = 2097152.

Checking 22 candidates per element is constant work. This turns what could be a hard pairing problem into a linear scan.

Approach: hash map complement lookup

The idea is the same as Two Sum, but generalized. For each element d in the array, you iterate over all 22 powers of 2 and check whether power - d already exists in a hash map. If it does, the count stored in the map tells you how many previous elements can pair with d to form that power of 2. After checking all powers, you add d itself to the map and move on.

This processes each element in O(22) = O(1) time, giving O(n) overall.

def count_pairs(deliciousness):
    MOD = 10**9 + 7
    count_map = {}
    result = 0

    for d in deliciousness:
        for i in range(22):
            power = 1 << i
            complement = power - d
            if complement in count_map:
                result = (result + count_map[complement]) % MOD
        count_map[d] = count_map.get(d, 0) + 1

    return result

Visual walkthrough

Notice how the algorithm never looks backward through the array. Each element checks the map (which stores everything before it), then adds itself. This avoids double-counting pairs and runs in a single pass.

Complexity analysis

Time is linear because the inner loop over 22 powers is constant. Space is O(n) in the worst case, when all values are distinct and every element ends up in the map.

Building blocks

1. Complement lookup (Two Sum pattern)

The core technique here is the same one that powers Two Sum. For a target value T and a current element d, you compute complement = T - d and check whether the complement exists in a hash map. The only difference is that instead of one fixed target, you loop over 22 targets (powers of 2).

complement = power - d
if complement in count_map:
    result += count_map[complement]

2. Enumerating powers of two

You need a fast way to generate all relevant powers of 2. Bit shifting is the cleanest approach. 1 << i gives you 2^i without any multiplication or exponentiation.

for i in range(22):
    power = 1 << i

The upper bound of 22 comes from the constraint that values are at most 2^20. Two such values sum to at most 2^21, and 2^21 is 1 << 21, so you need i from 0 to 21 inclusive.

Edge cases

• All zeros: pairs of zeros sum to 0, which is not a power of 2 (2^0 = 1), so the count is 0
• Duplicate values: if the array contains many copies of the same value, they form many pairs. For example, [8, 8, 8] has 3 pairs that sum to 16 = 2^4
• Large values: the count can grow very large with duplicates, so you must apply modular arithmetic (10^9 + 7) at each step to avoid overflow

From understanding to recall

Count Good Meals is a variation of the Two Sum complement lookup pattern. Once you see it broken down, the logic feels natural. But recognizing that a problem calls for "iterate over powers of 2 and check complements" under time pressure is a different skill from understanding the explanation.

Spaced repetition bridges that gap. By reconstructing the solution from memory at increasing intervals, you train yourself to reach for the right pattern automatically. After a few cycles, you will not need to re-derive the approach. The connection between "pair sums" and "hash map complement lookup" becomes second nature.

Related posts

• Two Sum - the foundational complement lookup pattern
• 4Sum II - hash map pairing across arrays
• K-diff Pairs in an Array - counting pairs with a hash map