Count Good Meals — Power-of-Two Complement HashMap

Problem 198 · Count Good Meals

Difficulty: Medium · Pattern: Complement Map (powers of 2)

Count pairs where sum is a power of 2. Return count mod 10^9+7.

Intuition

For each element, check all 22 possible powers of 2 (up to 2^21 ≈ 2M); add cnt[power - x] to answer.

Solutions

# Python
from collections import defaultdict
def countPairs(deliciousness):
    MOD = 10**9+7
    cnt = defaultdict(int)
    ans = 0
    for x in deliciousness:
        for p in range(22):
            ans = (ans + cnt[(1<<p) - x]) % MOD
        cnt[x] += 1
    return ans

// Java
public int countPairs(int[] deliciousness) {
    final int MOD = 1_000_000_007;
    Map<Integer,Integer> cnt = new HashMap<>();
    long ans = 0;
    for (int x : deliciousness) {
        for (int p = 0; p < 22; p++) {
            int target = (1<<p) - x;
            ans = (ans + cnt.getOrDefault(target, 0)) % MOD;
        }
        cnt.merge(x, 1, Integer::sum);
    }
    return (int)ans;
}

// C++
int countPairs(vector<int>& d) {
    const int MOD = 1e9+7;
    unordered_map<int,long> cnt;
    long ans = 0;
    for (int x : d) {
        for (int p = 0; p < 22; p++) {
            int t = (1<<p)-x;
            if (cnt.count(t)) ans = (ans+cnt[t])%MOD;
        }
        cnt[x]++;
    }
    return ans;
}

Complexity

Time: O(22n) = O(n)
Space: O(n)