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.

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= deliciousness.length &lt;= 105
	0 &lt;= deliciousness[i] &lt;= 220


class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        pows = [2 ** i for i in range(0,22)] # form our list of powers of 2
        dp_seen = {} # dict to store what we've seen - dynamic programming solution for time requirement
        count = 0 # to store the answer

        for j in range(0, len(deliciousness)):
            for i in range(0, len(pows)):
                if pows[i] - deliciousness[j] in dp_seen: # "if we find a previous deliciousness[j] as pows[i] - deliciousness[j], then we will add dp_seen[deliciousness[j]] to count"
                    count += dp_seen[pows[i] - deliciousness[j]]
            if deliciousness[j] in dp_seen:
                dp_seen[deliciousness[j]] += 1 
            else:
                dp_seen[deliciousness[j]] = 1
                
        return count % (10**9 + 7) # the arbitrary modulo, presumably to reduce the answer size
		```
class Solution {
    int mod = 1000000007;
    public int countPairs(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        long res = 0;
        for (int num : arr) {
            int power = 1;
            for (int i = 0; i < 22; i++) {
                if (map.containsKey(power - num)) {
                    res += map.get(power - num);
                    res %= mod;
                }
                power *= 2;
            }
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return (int) res;
    }
}
class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        int cnt=0;
        unordered_map<int,int> mp;
        mp[deliciousness[0]]++;
        int mod=1e9+7;
        for(int i=1;i<deliciousness.size();i++){
            for(int p=1;p<=(1<<21);p*=2){
                if(mp.find(p-deliciousness[i])!=mp.end()){
                    cnt=(cnt+mp[p-deliciousness[i]])%mod;
                    
                }
            }
            mp[deliciousness[i]]++;
            
        }
        return cnt%mod;
    }
};
var countPairs = function(deliciousness) {
    const n = deliciousness.length;
    const MOD = 1e9 + 7;

    const map = new Map();

    for (const num of deliciousness) {
        if (!map.has(num)) map.set(num, 0);
        map.set(num, map.get(num) + 1);
    }

    let max = 2**21;
    let res = 0;

    for (const [num, count] of map) {

        let two = 1;

        while (two <= max) {
            const diff = two - num;

            if (diff >= 0 && map.has(diff)) {

                const otherCount = map.get(diff);

                if (num != diff) res += (count * otherCount);
                else res += (count * (count - 1) / 2);
            }

            two <<= 1;
        }

        map.delete(num);
    }

    return res % MOD;
};
Count Good Meals