# Leetcode - Count Good Meals Solution

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`

item of food, return ^{th}*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 in Python

```
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
def sumOfAP(n):
return n*(n-1)//2
c = Counter(deliciousness)
powerOfTwos = {2**i for i in range(22)}
possibilities = 0
for x in c.keys():
if x*2 in powerOfTwos :
possibilities += sumOfAP(c[x])
for i in powerOfTwos:
y = i - x
if y != x and y>-1:
possibilities += c[x]*c[y]
c[x] = 0
return possibilities%(10**9 + 7)
```