Problem

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the ith item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Examples

Example 1:

1
2
3
4

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

1
2
3

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Solution

Method 1 - Solve Similar to Two Sum

Here is the approach:

  1. Similar to Two Sum, we need to find pairs whose sums are powers of 2.
  2. For each number in deliciousness, traverse all possible powers of 2: 2^i, where 0 <= i <= 21, and tally pairs using the hash map cnt.
  3. Record the count of the current number d in the hash map cnt.
  4. Noting that numbers in the array are ≤ 2^20, we use this to limit our search space.

Because 2^20 + 2^20 = 2^21, we need to check sums up to 2^21, handled by looping with i <= 21.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public int countPairs(int[] deliciousness) {
        // HashMap to keep count of each deliciousness value
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        final int MOD = 1_000_000_007;

        for (int d : deliciousness) {
            // Check pairs for all powers of two up to 2^21
            for (int power = 1, i = 0; i < 22; ++i, power <<= 1) {
                ans = (ans + cnt.getOrDefault(power - d, 0)) % MOD;
            }
            // Update count of current deliciousness value
            cnt.put(d, cnt.getOrDefault(d, 0) + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] deliciousness = {1, 3, 5, 7, 9};
        System.out.println("Number of good pairs: " + solution.countPairs(deliciousness)); // Output example
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countPairs(self, deliciousness):
        from collections import defaultdict
        
        cnt = defaultdict(int)
        ans = 0
        MOD = 1_000_000_007

        for d in deliciousness:
            # Check pairs for all powers of two up to 2^21
            for i in range(22):
                power = 1 << i
                ans = (ans + cnt[power - d]) % MOD
            # Update count of current deliciousness value
            cnt[d] += 1

        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)