Problem Description

You need to find pairs of food items whose combined deliciousness equals a power of 2 (like 1, 2, 4, 8, 16, 32, etc.).

Given an array deliciousness where each element represents the deliciousness value of a food item, you need to count how many different pairs of food items can form a "good meal". A good meal consists of exactly two different food items whose deliciousness values sum to a power of 2.

Key points to understand:

• You must pick exactly 2 different food items (different indices)
• Their sum must equal a power of 2 (e.g., 2^0 = 1, 2^1 = 2, 2^2 = 4, etc.)
• Items at different positions in the array are considered different, even if they have the same deliciousness value
• Return the total count modulo 10^9 + 7

For example, if you have deliciousness values [1, 3, 5, 7, 9]:

• Items at index 0 (value 1) and index 1 (value 3) sum to 4, which is 2^2, so this is a good meal
• Items at index 0 (value 1) and index 3 (value 7) sum to 8, which is 2^3, so this is also a good meal
• And so on...

The solution uses a hash table to track previously seen values and checks for each new element whether it can form a power of 2 with any previously seen element. For each element d, it checks all possible powers of 2 up to the maximum possible sum and looks for the complement (power_of_2 - d) in the hash table.

Intuition

The naive approach would be to check every pair of food items to see if their sum is a power of 2, but with up to 10^5 items, this O(n^2) approach would be too slow.

The key insight is that powers of 2 are limited. Since the maximum deliciousness value is at most 2^20, the maximum possible sum of two items is 2^20 + 2^20 = 2^21. This means we only need to check about 22 different power-of-2 values.

Instead of checking if the sum of every pair is a power of 2, we can flip the problem: for each food item with deliciousness d, we can check if there exists another item that would sum with d to make a specific power of 2.

For example, if we have a food item with deliciousness 3, and we want to check if it can form a sum of 8 (which is 2^3), we need to find if there's another item with deliciousness 8 - 3 = 5.

This leads us to use a hash table to track the frequency of deliciousness values we've already seen. As we iterate through the array:

1. For the current item d, we check all possible powers of 2 (from 1 up to twice the maximum value)
2. For each power of 2 value s, we check if s - d exists in our hash table
3. If it exists, we've found valid pairs - the count is how many times s - d appeared before
4. After checking all powers of 2 for the current item, we add it to our hash table for future items to pair with

This approach is efficient because:

• We only traverse the array once: O(n)
• For each element, we only check about 22 powers of 2: O(log M) where M is the maximum value
• Hash table lookups are O(1)

The total time complexity becomes O(n × log M), which is much better than the naive O(n^2).

Solution Approach

The solution uses a hash table combined with enumeration of powers of 2. Here's how the implementation works:

Data Structure Used:

• A Counter (hash table) to track the frequency of each deliciousness value we've encountered

Algorithm Steps:

1. Initialize variables:

   • mod = 10^9 + 7 for the modulo operation
   • mx = max(deliciousness) << 1 calculates twice the maximum value (left shift by 1 is equivalent to multiplying by 2). This represents the maximum possible sum we need to check
   • cnt = Counter() creates an empty hash table to store frequencies
   • ans = 0 to accumulate the count of valid pairs

2. Main iteration through the array: For each deliciousness value d:

   a. Check all powers of 2:

   • Start with s = 1 (which is 2^0)
   • While s <= mx:
     • Check if s - d exists in the hash table
     • If it exists, add cnt[s - d] to the answer (this represents all the previous items that can pair with d to form sum s)
     • Double s by left shifting (s <<= 1) to get the next power of 2

   b. Update the hash table:

   • After checking all possible powers of 2 for the current element, increment cnt[d] by 1
   • This ensures the current element can be paired with future elements

3. Return the result:

   • Return ans % mod

Why this order matters:

• We update the hash table after checking for pairs to avoid counting a pair twice
• By processing elements one by one and only looking at previously seen elements, we ensure each pair (i, j) where i < j is counted exactly once

Example walkthrough: If deliciousness = [1, 3, 5, 7, 9]:

• Process 1: No previous elements, add 1 to hash table
• Process 3: Check if 1-3=-2, 2-3=-1, 4-3=1 (found!), 8-3=5, etc. Find 1 in hash table, so ans += 1
• Process 5: Check powers of 2, find 8-5=3 exists, so ans += 1
• And so on...

The time complexity is O(n × log M) where n is the array length and M is the maximum value, since for each element we check at most log M powers of 2.

Example Walkthrough

Let's walk through a small example with deliciousness = [1, 3, 5, 7, 9].

Initial Setup:

• mx = max(1,3,5,7,9) × 2 = 9 × 2 = 18
• cnt = {} (empty hash table)
• ans = 0

Step 1: Process element 1

• Check powers of 2: 1, 2, 4, 8, 16
  • 1 - 1 = 0: not in cnt
  • 2 - 1 = 1: not in cnt
  • 4 - 1 = 3: not in cnt
  • 8 - 1 = 7: not in cnt
  • 16 - 1 = 15: not in cnt
• Update cnt: {1: 1}
• ans remains 0

Step 2: Process element 3

• Check powers of 2: 1, 2, 4, 8, 16
  • 1 - 3 = -2: negative, skip
  • 2 - 3 = -1: negative, skip
  • 4 - 3 = 1: found in cnt! ans += cnt[1] = 1
  • 8 - 3 = 5: not in cnt
  • 16 - 3 = 13: not in cnt
• Update cnt: {1: 1, 3: 1}
• ans = 1 (pair: indices 0,1 with values 1+3=4)

Step 3: Process element 5

• Check powers of 2: 1, 2, 4, 8, 16
  • 1 - 5 = -4: negative, skip
  • 2 - 5 = -3: negative, skip
  • 4 - 5 = -1: negative, skip
  • 8 - 5 = 3: found in cnt! ans += cnt[3] = 1
  • 16 - 5 = 11: not in cnt
• Update cnt: {1: 1, 3: 1, 5: 1}
• ans = 2 (new pair: indices 1,2 with values 3+5=8)

Step 4: Process element 7

• Check powers of 2: 1, 2, 4, 8, 16
  • 1 - 7 = -6: negative, skip
  • 2 - 7 = -5: negative, skip
  • 4 - 7 = -3: negative, skip
  • 8 - 7 = 1: found in cnt! ans += cnt[1] = 1
  • 16 - 7 = 9: not in cnt
• Update cnt: {1: 1, 3: 1, 5: 1, 7: 1}
• ans = 3 (new pair: indices 0,3 with values 1+7=8)

Step 5: Process element 9

• Check powers of 2: 1, 2, 4, 8, 16
  • 1 - 9 = -8: negative, skip
  • 2 - 9 = -7: negative, skip
  • 4 - 9 = -5: negative, skip
  • 8 - 9 = -1: negative, skip
  • 16 - 9 = 7: found in cnt! ans += cnt[7] = 1
• Update cnt: {1: 1, 3: 1, 5: 1, 7: 1, 9: 1}
• ans = 4 (new pair: indices 3,4 with values 7+9=16)

Final Result: 4 good meals

• (1, 3) → 4 = 2²
• (3, 5) → 8 = 2³
• (1, 7) → 8 = 2³
• (7, 9) → 16 = 2⁴

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log(max_value))

• The outer loop iterates through all n elements in the deliciousness array
• For each element d, the inner while loop runs while s <= mx, where mx = max(deliciousness) * 2
• Since s starts at 1 and doubles each iteration (s <<= 1), it takes O(log(mx)) iterations to reach mx
• The maximum value in the array determines mx, so we can say the inner loop runs O(log(max_value)) times
• Operations inside the loops (Counter lookup and addition) are O(1)
• Total time complexity: O(n * log(max_value))

Space Complexity: O(n)

• The Counter object cnt stores at most n unique elements from the deliciousness array
• Each unique value appears as a key in the counter with its frequency as the value
• Other variables (mod, mx, ans, d, s) use constant space O(1)
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Counting Pairs Twice

Pitfall: A common mistake is to iterate through all elements and check all other elements, which would count each pair twice (once as (i,j) and once as (j,i)).

Wrong Approach:

# This counts each pair twice!
for i in range(len(deliciousness)):
    for j in range(len(deliciousness)):
        if i != j and is_power_of_two(deliciousness[i] + deliciousness[j]):
            result += 1

Solution: Process elements sequentially and only look at previously seen elements in the hash table. Update the hash table after checking, not before.

2. Incorrect Maximum Sum Calculation

Pitfall: Using just the maximum element value as the upper bound for powers of 2, which would miss valid pairs.

Wrong:

max_sum = max(deliciousness)  # Wrong! Misses pairs like [2^20, 2^20]

Correct:

max_sum = max(deliciousness) * 2  # Correct upper bound

3. Forgetting Modulo Operation

Pitfall: Only applying modulo at the final return, which can cause integer overflow in languages with fixed integer sizes.

Wrong:

result = result + count_map[complement]  # Can overflow
return result % MOD  # Too late!

Correct:

result = (result + count_map[complement]) % MOD  # Apply modulo immediately

4. Using Set Instead of Counter

Pitfall: Using a set to track seen values loses frequency information, making it impossible to count multiple occurrences correctly.

Wrong:

seen = set()
for d in deliciousness:
    # This only counts unique values, not frequencies!
    if complement in seen:
        result += 1
    seen.add(d)

Correct: Use Counter or a dictionary to track frequencies of each value.

5. Checking Non-Powers of 2

Pitfall: Iterating through all numbers up to max_sum instead of just powers of 2, causing time limit exceeded.

Wrong:

for possible_sum in range(1, max_sum + 1):
    if is_power_of_two(possible_sum):  # Inefficient!
        complement = possible_sum - current_value

Correct:

power_of_two = 1
while power_of_two <= max_sum:
    complement = power_of_two - current_value
    # ... check complement ...
    power_of_two <<= 1  # Efficiently jump to next power of 2

6. Including Negative Complements

Pitfall: Not handling cases where the complement would be negative (when current value > power of 2).

Note: While Python's Counter handles negative keys gracefully by returning 0, it's good practice to be aware that power_of_two - current_value can be negative, and in some implementations, you might want to add a check:

if complement >= 0 and complement in count_map:
    result += count_map[complement]