Count Good Meals — Power-of-Two Complement Counting

Problem Statement#

A good meal contains exactly two different food items with a total deliciousness equal to a power of two. You can pick any two different items to make a good meal.

Given an array deliciousness where deliciousness[i] is the deliciousness of the ith item, return the number of different good meals you can make modulo 10^9 + 7.

Items at different indices are considered different even if they have the same deliciousness value.

Constraints:

• 1 <= deliciousness.length <= 10^5
• 0 <= deliciousness[i] <= 2^20

Input:  deliciousness = [1,3,5,7,9]
Output: 4
Explanation: Pairs: (1,3)=4=2^2, (1,7)=8=2^3, (3,5)=8=2^3, (7,9)=16=2^4.

Input:  deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: 1+1=2: C(3,2)=3 pairs. 1+3=4: 3x3=9 pairs. 1+7=8: 3 pairs. Total=15.

Why This Problem Matters#

Count Good Meals (LC 1711) is a direct extension of the classic Two Sum problem with a twist: instead of checking one target, you check 22 possible targets — all powers of 2 up to 2^21. This bounded number of targets is the key that keeps the algorithm O(n) despite the unknown target.

Amazon and Google use this problem in interviews because it tests bit manipulation awareness (knowing which powers of 2 are relevant), complement counting (the Two Sum pattern), and modular arithmetic for large counts. The combination of these three skills in one problem makes it a reliable signal of a well-rounded candidate.

Why 22 powers of 2? The maximum deliciousness is 2^20. The maximum sum of two items is 2 × 2^20 = 2^21. Powers of 2 from 2^0 through 2^21 cover all possible sums — 22 values total. At Meta, this type of bounded enumeration appears in data engineering screens: instead of checking all possible values, check only the small set of "interesting" values — a fundamental technique in number theory and combinatorics-based algorithms.

The Core Insight#

For each element x, check all 22 powers of 2: 2^0, 2^1, ..., 2^21. For each power p, the complement is p - x. If p - x has appeared before in the frequency map, then freq[p - x] new good meals can be formed by pairing any previous occurrence of p - x with the current x.

After checking all 22 powers, add x to the frequency map.

This is the Two Sum pattern applied 22 times per element. Since 22 is a constant, the total time is O(22n) = O(n).

Why add x to the map AFTER checking? To avoid counting a pairing of x with itself. If we added first, checking freq[p - x] when p - x == x would incorrectly count the current element.

Visual Dry Run#

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

Total = 4. Pairs: (1,3)=4, (3,5)=8, (1,7)=8, (7,9)=16.

Solution (Optimal)#

from collections import defaultdict
 
def countPairs(deliciousness: list[int]) -> int:
    MOD = 10**9 + 7
    freq = defaultdict(int)
    ans = 0
 
    for x in deliciousness:
        for power in range(22):
            target = 1 << power  # 2^power
            complement = target - x
            if complement >= 0:
                ans = (ans + freq[complement]) % MOD
        freq[x] += 1
 
    return ans

var countPairs = function(deliciousness) {
    const MOD = 1_000_000_007n;
    const freq = new Map();
    let ans = 0n;
 
    for (const x of deliciousness) {
        for (let power = 0; power < 22; power++) {
            const target = 1 << power;
            const complement = target - x;
            if (complement >= 0 && freq.has(complement)) {
                ans = (ans + BigInt(freq.get(complement))) % MOD;
            }
        }
        freq.set(x, (freq.get(x) || 0) + 1);
    }
 
    return Number(ans);
};

Time: O(22n) = O(n) — check 22 powers per element. Space: O(n) — frequency map stores at most n distinct values.

Common Mistakes#

• Adding x to freq before checking: Would allow pairing an element with itself. Always check all 22 powers first, then add.
• Forgetting the modulo: Answer can reach O(n²) ≈ 10^10, which overflows 32-bit integers. Apply modulo at each step.
• Wrong upper bound for powers: Maximum sum is 2^20 + 2^20 = 2^21. Check powers 0 through 21 inclusive — that is 22 values. Using only up to 20 misses the case where both elements are 2^20.
• Not filtering negative complements: Deliciousness is non-negative. If p - x < 0, skip. No valid complement exists.
• JavaScript integer overflow for large answers: Pair count can exceed 2^53 (safe integer limit). Use BigInt or apply modulo frequently.

Interview Tips#

• Explain why 22 powers suffice before coding — this shows you analysed the constraints.
• Mention the "check-then-add" ordering and why it prevents self-pairing.
• Compare to Two Sum explicitly: "This is Two Sum repeated for 22 different targets."
• Note that the pattern generalises: for powers of 3, compute the appropriate upper bound and check that many values.

Follow-up Questions#

• What if the problem asked for sums equal to powers of 3? Check log₃(2 × 2^20) ≈ 12-13 powers of 3. Same approach, different upper bound.
• Can you find the actual pairs, not just count them? Store element indices rather than just frequencies, then retrieve the complement's index when a match is found.
• How would you adapt this to count triples summing to a power of 2? O(22n²) — fix two elements, check if the complement is in the frequency map.
• What is the maximum possible answer for n = 10^5? C(10^5, 2) ≈ 5×10^9 pairs maximum, returned modulo 10^9+7.
• How does this problem relate to subset-sum with bounded targets? Bounded enumeration — check only the small set of "interesting" target values — is the same technique used here.

Key Takeaways#

• Count Good Meals (LC 1711) extends Two Sum to 22 power-of-two targets using a frequency map and complement lookup.
• The upper bound is 22 powers (2^0 through 2^21) because the maximum element is 2^20 and the maximum sum is 2^21.
• Always add x to the frequency map AFTER checking all 22 powers to prevent self-pairing.
• Time O(n), space O(n) — the 22-constant inner loop is absorbed into the O notation.
• Apply modulo at each accumulation step to prevent integer overflow on large inputs.
• In JavaScript, use BigInt for the accumulator when pair counts could exceed 2^53.
• The bounded enumeration technique — checking only a small constant number of "interesting" targets — is a fundamental pattern in number theory and combinatorics problems.