# Count Good Meals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-good-meals)
Canonical: https://scaleengineer.com/dsa/problems/count-good-meals
**Data structures:** Array, Hash Table
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy), [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## 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 `i​​​​​​th​​​​`​​​​ 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.

**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 <= 105`
* `0 <= deliciousness[i] <= 220`

# Approaches
## Brute Force Iteration
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible pair of different food items, calculating the sum of their deliciousness, and verifying if that sum is a power of two.
**Time:** O(N^2), where N is the length of the `deliciousness` array. The two nested loops result in a quadratic number of pairs to check. · **Space:** O(1), as it only uses a few variables to store loop indices and the count, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory-efficient.
**Cons:** This approach is very slow due to the nested loops, resulting in a quadratic time complexity.; It will not pass the time limits for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' (TLE) error.
### Explanation
This method uses two nested loops to generate all unique pairs of food items. The outer loop runs from `i = 0` to `n-2` and the inner loop runs from `j = i + 1` to `n-1`, where `n` is the number of food items. This ensures that every pair `(i, j)` is considered exactly once.

For each pair, we compute the sum of their deliciousness values. We then need a way to check if this sum is a power of two. A common and efficient way to do this is using a bitwise trick: a positive integer `x` is a power of two if and only if the expression `(x & (x - 1))` equals zero. If the sum satisfies this condition, we increment a counter.

Finally, after checking all pairs, the total count is returned. Since the result can be large, it should be taken modulo `10^9 + 7`, although with this approach, the count variable is unlikely to overflow before the program times out.

```java
class Solution {
    public int countPairs(int[] deliciousness) {
        int n = deliciousness.length;
        long count = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long sum = (long) deliciousness[i] + deliciousness[j];
                // Check if sum is a power of two
                if (sum > 0 && (sum & (sum - 1)) == 0) {
                    count++;
                }
            }
        }
        return (int) (count % MOD);
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Initialize `MOD = 1_000_000_007`.
- Use a nested loop to iterate through all pairs of indices `(i, j)` such that `i < j`.
- For each pair, calculate the sum `s = deliciousness[i] + deliciousness[j]`.
- Check if the sum `s` is a power of two. A positive integer `s` is a power of two if and only if `s > 0 && (s & (s - 1)) == 0`.
- If `s` is a power of two, increment the `count`.
- After the loops complete, return the final `count`.

## Hash Map and Powers of Two
A much more efficient approach utilizes a hash map to optimize the search for pairs. Instead of iterating through all pairs, for each number, we can directly calculate the complement needed to form a power-of-two sum and check if we have seen that complement before.
**Time:** O(N * K), where N is the number of food items and K is the number of powers of two to check. Since K is a small constant (22), the time complexity is effectively linear, O(N). · **Space:** O(U), where U is the number of unique elements in the `deliciousness` array. In the worst-case scenario where all elements are distinct, the space complexity is O(N).
**Pros:** Significantly more efficient than the brute-force approach, with a linear time complexity.; Passes the time limits for the given constraints.; Elegantly handles duplicate values and avoids double-counting pairs.
**Cons:** Requires extra space to store the frequency map, which can be up to O(N) in the worst case where all elements are unique.
### Explanation
This approach is based on the two-sum problem pattern. We iterate through the `deliciousness` array, and for each element `d`, we try to find a partner `target` such that `d + target` is a power of two.

We maintain a hash map, `freqMap`, to keep track of the frequencies of the numbers we have processed so far. When we are at a number `d`, we iterate through a list of possible powers of two that the sum could equal. The maximum possible sum is `2^20 + 2^20 = 2^21`, so we only need to check powers of two from `2^0` up to `2^21` (a total of 22 powers).

For each power of two `p`, we calculate the needed complement `target = p - d`. We then check our `freqMap` for the existence of this `target`. If it exists, we add its frequency (the value in the map) to our total count of good meals. This is because every occurrence of `target` we've seen so far can form a good meal with the current `d`.

After checking all possible powers of two for the current number `d`, we update its own frequency in the `freqMap`. This single-pass process ensures that we count each pair `(i, j)` with `i != j` exactly once and avoids double counting.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countPairs(int[] deliciousness) {
        int MOD = 1_000_000_007;
        Map<Integer, Integer> freqMap = new HashMap<>();
        long count = 0;

        for (int d : deliciousness) {
            for (int i = 0; i <= 21; i++) {
                int powerOfTwo = 1 << i;
                int target = powerOfTwo - d;

                if (freqMap.containsKey(target)) {
                    count += freqMap.get(target);
                }
            }
            // It's important to apply modulo after additions to prevent overflow, 
            // though here we do it at the end for simplicity as intermediate count fits long.
            // A safer way is count %= MOD after each addition.
            freqMap.put(d, freqMap.getOrDefault(d, 0) + 1);
        }

        return (int) (count % MOD);
    }
}
```
### Algorithm
- Initialize a hash map, `freqMap`, to store the frequency of each deliciousness value.
- Initialize a `long` counter `count` to 0 and `MOD = 1_000_000_007`.
- Iterate through each number `d` in the `deliciousness` array.
- For each `d`, iterate through all possible target powers of two, `p`, that the sum can form. The maximum sum is `2^20 + 2^20 = 2^21`, so we check powers from `2^0` to `2^21`.
- For each power of two `p`, calculate the required complement `target = p - d`.
- If `freqMap` contains the key `target`, it means we have found `freqMap.get(target)` numbers that can be paired with the current `d`. Add this frequency to `count`.
- After checking all powers of two for the current `d`, update its frequency in `freqMap`. This makes it available for subsequent elements.
- After iterating through all elements, return `(int) count % MOD`.

# Solutions
### Python

```python
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int: mod = 10 ** 9 + 7 mx = max(deliciousness) << 1 cnt = Counter() ans = 0 for d in deliciousness: s = 1 while s <= mx: ans = (ans + cnt[s - d]) % mod s <<= 1 cnt[d] += 1 return ans

```

### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int countPairs(int[] deliciousness) {
    int mx = Arrays.stream(deliciousness).max().getAsInt() << 1;
    int ans = 0;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int d : deliciousness) {
      for (int s = 1; s <= mx; s <<= 1) {
        ans = (ans + cnt.getOrDefault(s - d, 0)) % MOD;
      }
      cnt.merge(d, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int countPairs(vector<int> &deliciousness) {
    int mx = *max_element(deliciousness.begin(), deliciousness.end()) << 1;
    unordered_map<int, int> cnt;
    int ans = 0;
    for (auto &d : deliciousness) {
      for (int s = 1; s <= mx; s <<= 1) {
        ans = (ans + cnt[s - d]) % mod;
      }
      ++cnt[d];
    }
    return ans;
  }
};

```