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

<p>You can pick <strong>any</strong> two different foods to make a good meal.</p>

<p>Given an array of integers <code>deliciousness</code> where <code>deliciousness[i]</code> is the deliciousness of the <code>i<sup>​​​​​​th</sup>​​​​</code>​​​​ item of food, return <em>the number of different <strong>good meals</strong> you can make from this list modulo</em> <code>10<sup>9</sup> + 7</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> deliciousness = [1,3,5,7,9]
<strong>Output:</strong> 4
<strong>Explanation: </strong>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.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= deliciousness.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= deliciousness[i] &lt;= 2<sup>20</sup></code></li>
</ul>

"""
good meal == 1) len(meal) == 2, 2) sum of two meals is a power of two
return: number of good meals modulo 10^9 + 7
Powers of Two: Powers of two are numbers like 1, 2, 4, 8, 16, 32, etc. These numbers have binary representations with exactly one bit set, such as 0001, 0010, 0100, etc.
"""
from typing import List
from collections import defaultdict

class Solution:
    """
    Time: O(nlogm) or O(n), since logm is the number of powers of 2 we check (which is constant)
    Space: O(u), where u is the number of unique deliciousness values
    """
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 10**9 + 7
        
        # Precompute all powers of two up to the maximum possible sum
        powers_of_two = [1 << i for i in range(22)]  # {1, 2, 4, 8, 16, 32, ..., 2^21}
        # or
        # powers_of_two = [2 ** i for i in range(22)]

        # Frequency dictionary to keep count of each deliciousness value
        freq = defaultdict(int)
        count = 0
        
        # Loop through each food item
        for val in deliciousness:
            # Check all possible pairs where val + another_val is a power of two
            for power in powers_of_two:
                complement = power - val
                if complement in freq:
                    count = count + freq[complement]
            
            # Record the current value in the frequency dictionary
            freq[val] += 1
        
        return count % MOD
1005