Count Good Meals

return count of set of meals whose deliciousness score (sum of both meals) is power of 2

Count Good Meals

Problem

A good meal has exactly two different food items, and the sum of their deliciousness is a power of two.

You are given an array deliciousness. The value deliciousness[i] is the deliciousness of the ith food item.

Return the number of different good meals you can make, modulo 10^9 + 7.

Items with different indexes are different, even if their values are the same.

Examples

Example 1

Input: deliciousness = [1,3,5,7,9]
Output: 4

• (1,3) has sum 4.
• (1,7) has sum 8.
• (3,5) has sum 8.
• (7,9) has sum 16.
• All sums are powers of two, so the answer is 4.

Example 2

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15

• (1,1) can be made in 3 ways. The sum is 2.
• (1,3) can be made in 9 ways. The sum is 4.
• (1,7) can be made in 3 ways. The sum is 8.
• Total = 3 + 9 + 3 = 15.

Constraints

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

Main Idea

This is a Two Sum problem with a twist. Instead of one target, we have many targets: 1, 2, 4, 8, 16, ....

For each number num, and for each power of two power, we ask:

"Have I already seen the number power - num?"

• We keep a hash map that stores each value and how many times we saw it.
• If complement = power - num is in the map, we can make that many good meals with num.
• We add the count to the answer.
• After we check all powers, we add num to the map.

Why we count only earlier items

• We check the map before adding the current number.
• So each pair is counted once, when its second item arrives.
• Also, a number is never paired with itself.

How many powers do we check?

• The biggest sum is max + max = 2 * max.
• So we check powers of two from 1 up to 2 * max.
• Since max <= 2^20, there are at most 22 powers (2^0 to 2^21).
• That is a small fixed number.

Solution 1: Brute Force

We check every pair of items. A sum is a power of two if sum > 0 and sum & (sum - 1) === 0.

var countPairs = function (deliciousness) {
    let output = 0;

    for (let i = 0; i < deliciousness.length; i++) {
        for (let j = i + 1; j < deliciousness.length; j++) {
            let sum = deliciousness[i] + deliciousness[j];

            if (sum > 0 && (sum & (sum - 1)) === 0) {
                output++;
            }
        }
    }

    return output;
};

How the Power of Two Check Works

• A power of two has only one bit set in binary. For example, 8 is 1000.
• sum - 1 flips that bit and sets all the bits after it. For example, 7 is 0111.
• So sum & (sum - 1) is 0 only for a power of two.
• We need sum > 0, because 0 & -1 is also 0, but 0 is not a power of two.

Complexity

• Time Complexity: O(n²)
  • n is the number of food items.
  • We check every pair. With n = 10^5, this is about 5 * 10^9 pairs, which is too slow.
• Space Complexity: O(1)
  • We use only a few variables.

Note: This version does not use % MOD. For large inputs the count can pass 10^9 + 7, so it would give a wrong answer. It is only good for small inputs.

Solution 2: Hash Map (Optimal)

var countPairs = function (deliciousness) {
    let map = new Map();
    let output = 0;
    let MOD = 1e9 + 7;

    let max = Math.max(...deliciousness);

    for (let num of deliciousness) {
        // try every power of two that can be a sum
        for (let power = 1; power <= max * 2; power *= 2) {
            let complement = power - num;

            // the partner was seen before
            if (map.has(complement)) {
                output = (output + map.get(complement)) % MOD;
            }
        }

        // save the current number
        map.set(num, (map.get(num) || 0) + 1);
    }

    return output;
};

How the Code Works

Step 1: Set up

• map stores each value and how many times we saw it.
• output is the answer. MOD is 10^9 + 7.
• max is the biggest value. The biggest possible sum is max * 2.

Step 2: Read each number

• For each num, we try power = 1, 2, 4, 8, ... up to max * 2.
• power *= 2 moves to the next power of two.

Step 3: Find the partner

• complement = power - num is the value we need to reach this power.
• If it is negative, it is never in the map, so nothing happens.
• If it is in the map, map.get(complement) tells us how many earlier items have this value.
• Each of them makes a different good meal with the current item, so we add that count.
• We use % MOD to keep the number small.

Step 4: Save the number

• We add num to the map after the loop over powers.
• This way, the current item is not paired with itself.

Step 5: Return the answer

• output holds the total number of good meals.

Dry Run

Let us take deliciousness = [1, 3, 5, 7, 9].

Here max = 9, so we check powers 1, 2, 4, 8, 16.

The answer is 4.

Now let us look at repeated values. Take [1, 1, 1].

• First 1: the map is empty, so we add nothing. Map is {1: 1}.
• Second 1: the power 2 needs 1, and the map has one 1. We add 1. Map is {1: 2}.
• Third 1: the power 2 needs 1, and the map has two 1s. We add 2. Total = 3.

This gives 3 pairs, which is correct, because three items make 3 pairs.

Complexity

• Time Complexity: O(n * log(max))
  • n is the number of items and max is the biggest value.
  • For each item, we check about log2(2 * max) powers. This is at most 22.
  • Each map operation takes O(1) on average.
  • So it is close to O(n), because 22 is a fixed small number.
• Space Complexity: O(n)
  • The map holds one entry for each different value, which is at most n.

Tip: Math.max(...deliciousness) works for 10^5 items, but it can fail with much bigger arrays. A simple loop to find the max is safer.

Comparison

Summary

• A good meal is a pair of items whose sum is a power of two.
• This is like Two Sum, but with many targets: 1, 2, 4, 8, ....
• There are at most about 22 powers, because the sum is at most 2^21.
• For each item, we check each power and look for power - num in the map.
• We save the current item after checking, so every pair is counted once.
• The map stores counts, so repeated values give the correct number of pairs.
• We use % MOD on the answer.
• Brute force takes O(n²) time and is too slow. The hash map solution runs in O(n * log(max)) time and uses O(n) space.