Formatted question description: https://leetcode.ca/all/1711.html

# 1711. Count Good Meals

## Level

Medium

## Description

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 `i-th`

item of food, return *the number of different good meals you can make from this list modulo 10^9 + 7*.

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

**Example 1:**

**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:**

**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.

**Constraints:**

`1 <= deliciousness.length <= 10^5`

`0 <= deliciousness[i] <= 2^20`

## Solution

Use a map to store each deliciousness’ number of occurrences and maintain the maximum deliciousness. Loop over `deliciousness`

. For each element, obtain all the elements that are greater than or equal to the current element such that the sum of the current element and the other element is a power of two, and update the number of good meals. Finally, return the number of good meals.

```
class Solution {
public int countPairs(int[] deliciousness) {
final int MODULO = 1000000007;
Map<Integer, Long> map = new HashMap<Integer, Long>();
int max = 0;
for (int num : deliciousness) {
long count = map.getOrDefault(num, 0L) + 1;
map.put(num, count);
max = Math.max(max, num);
}
long pairs = 0;
Set<Integer> keySet = map.keySet();
for (int num : keySet) {
long count = map.get(num);
if (num > 0 && (num & (num - 1)) == 0)
pairs = (pairs + count * (count - 1) / 2) % MODULO;
int power2 = 1;
while (power2 <= num * 2)
power2 <<= 1;
int upper = num + max;
while (power2 <= upper) {
int complement = power2 - num;
if (map.containsKey(complement)) {
long complementCount = map.get(complement);
pairs = (pairs + count * complementCount) % MODULO;
}
power2 <<= 1;
}
}
return (int) pairs;
}
}
```