Problem Description

You are given an integer array deliciousness, where each element represents the "deliciousness" value of a dish. A good meal is a pair of dishes (i, j) such that i < j and the sum of their deliciousness values is a power of two (i.e., 1, 2, 4, 8, ...).

Your task is to count the total number of good meals that can be made from the array. Since the answer may be large, return it modulo 10^9 + 7.

Key constraints:

• You cannot reuse the same dish in a pair (indices must be distinct).
• Each pair is counted only once (i.e., (i, j) and (j, i) are considered the same if i < j).
• There is no guarantee that a good meal exists; you must count all possible pairs.

Thought Process

At first glance, you might think of checking all possible pairs in the array and seeing if their sum is a power of two. However, with up to 10⁵ elements, this brute-force approach would require checking about 5 billion pairs, which is far too slow.

To optimize, consider the following insights:

• For each dish, you want to know: "How many previous dishes could pair with this one to sum to a power of two?"
• Instead of checking all pairs, you can count how many times a "complement" value has occurred so far, using a hash map.
• This is similar to the classic "two sum" problem, but instead of a fixed target, the target can be any power of two.

Solution Approach

Here’s a step-by-step breakdown of the efficient algorithm:

1. Precompute all possible target sums:
   • Since deliciousness values can be up to 2²⁰, the largest possible sum is 2²¹. So, generate all powers of two up to 2²¹.
2. Use a hash map to count occurrences:
   • As you iterate through the array, for each current value, check for each possible power of two: "How many times have I seen (target_sum - current_value) before?" If so, add that count to your answer.
   • After checking, record the current value in the hash map for future pairs.
3. Modulo operation:
   • Since the answer can be large, take modulo 10⁹+7 at each step.

This approach ensures each pair is counted exactly once and leverages fast hash map lookups for efficiency.

Example Walkthrough

Example Input: deliciousness = [1, 3, 5, 7, 9]
All possible powers of two up to 16: 1, 2, 4, 8, 16

Let's walk through each element:

• First value (1): No previous values, so no pairs.
• Second value (3):
  • For target sum 4: 4 - 3 = 1. Have we seen 1 before? Yes, once. So, one good meal.
• Third value (5):
  • For target sum 8: 8 - 5 = 3. Have we seen 3 before? Yes, once. So, one good meal.
• Fourth value (7):
  • For target sum 8: 8 - 7 = 1. Have we seen 1 before? Yes, once. So, one good meal.
• Fifth value (9):
  • For target sum 16: 16 - 9 = 7. Have we seen 7 before? Yes, once. So, one good meal.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N²) due to checking all pairs.
  • Space: O(1) extra space.
• Optimized approach (using hash map):
  • Time: O(N * K), where N is the number of dishes and K is the number of powers of two (at most 22 for 32-bit integers). For practical purposes, this is linear.
  • Space: O(N) for the hash map storing counts of previous values.

The optimized approach is much more efficient and suitable for large input sizes.

Summary

To efficiently count "good meals," we avoid brute-force pair checks by using a hash map to remember how often each value has occurred. For each dish, we look for complements that would sum to a power of two, using precomputed targets. This approach is both simple and powerful, turning an otherwise intractable problem into a quick linear scan.

The key insight is to realize the problem is a variant of "two sum" with multiple possible targets, and leveraging hash maps makes it fast and elegant.

Code Implementation

class Solution:
    def countPairs(self, deliciousness):
        from collections import defaultdict
        MOD = 10 ** 9 + 7
        max_val = max(deliciousness)
        max_sum = max_val * 2
        powers = [1 << i for i in range(22)]
        count = defaultdict(int)
        ans = 0
        for num in deliciousness:
            for target in powers:
                complement = target - num
                ans = (ans + count[complement]) % MOD
            count[num] += 1
        return ans
      

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int, int> count;
        int MOD = 1e9 + 7;
        int max_val = *max_element(deliciousness.begin(), deliciousness.end());
        int max_sum = max_val * 2;
        int ans = 0;
        for (int num : deliciousness) {
            for (int i = 0; i <= 21; ++i) {
                int target = 1 << i;
                int complement = target - num;
                if (count.count(complement)) {
                    ans = (ans + count[complement]) % MOD;
                }
            }
            count[num]++;
        }
        return ans;
    }
};
      

class Solution {
    public int countPairs(int[] deliciousness) {
        int MOD = 1000000007;
        int maxVal = 0;
        for (int num : deliciousness) maxVal = Math.max(maxVal, num);
        int maxSum = maxVal * 2;
        Map<Integer, Integer> count = new HashMap<>();
        int ans = 0;
        for (int num : deliciousness) {
            for (int i = 0; i <= 21; i++) {
                int target = 1 << i;
                int complement = target - num;
                ans = (ans + count.getOrDefault(complement, 0)) % MOD;
            }
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        return ans;
    }
}
      

var countPairs = function(deliciousness) {
    const MOD = 1e9 + 7;
    let maxVal = Math.max(...deliciousness);
    let maxSum = maxVal * 2;
    let count = new Map();
    let ans = 0;
    for (let num of deliciousness) {
        for (let i = 0; i <= 21; ++i) {
            let target = 1 << i;
            let complement = target - num;
            if (count.has(complement)) {
                ans = (ans + count.get(complement)) % MOD;
            }
        }
        count.set(num, (count.get(num) || 0) + 1);
    }
    return ans;
};