1711. Count Good Meals

MediumArrayHash Table

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

For each deliciousness value, look up complements that make a power of two using a running frequency map.

Open in Flowchart

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:

For the current item d, we check all possible powers of 2 (from 1 up to twice the maximum value)
For each power of 2 value s, we check if s - d exists in our hash table
If it exists, we've found valid pairs - the count is how many times s - d appeared before
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:

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
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
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

1class Solution:
2    def countPairs(self, deliciousness: List[int]) -> int:
3        """
4        Count pairs of meals where the sum is a power of two.
5      
6        Args:
7            deliciousness: List of integers representing deliciousness values
8          
9        Returns:
10            Number of valid pairs modulo 10^9 + 7
11        """
12        MOD = 10**9 + 7
13      
14        # Maximum possible sum is twice the maximum element
15        max_sum = max(deliciousness) * 2
16      
17        # Dictionary to count occurrences of each deliciousness value
18        count_map = Counter()
19        result = 0
20      
21        # Process each deliciousness value
22        for current_value in deliciousness:
23            # Check all powers of 2 up to max_sum
24            power_of_two = 1
25            while power_of_two <= max_sum:
26                # Find complement that would sum to power_of_two
27                complement = power_of_two - current_value
28              
29                # Add count of complements seen so far
30                result = (result + count_map[complement]) % MOD
31              
32                # Move to next power of 2
33                power_of_two <<= 1
34          
35            # Add current value to the count map for future pairs
36            count_map[current_value] += 1
37      
38        return result
39

1class Solution {
2    // Modulo value for preventing integer overflow
3    private static final int MOD = (int) 1e9 + 7;
4
5    public int countPairs(int[] deliciousness) {
6        // Find the maximum value and multiply by 2 to get the upper bound of possible power-of-2 sums
7        int maxValue = Arrays.stream(deliciousness).max().getAsInt();
8        int maxPossibleSum = maxValue << 1; // Equivalent to maxValue * 2
9      
10        // Initialize the result counter
11        int result = 0;
12      
13        // HashMap to store the frequency of each deliciousness value encountered so far
14        Map<Integer, Integer> frequencyMap = new HashMap<>();
15      
16        // Iterate through each deliciousness value
17        for (int currentDeliciousness : deliciousness) {
18            // Check all possible powers of 2 up to maxPossibleSum
19            for (int powerOfTwo = 1; powerOfTwo <= maxPossibleSum; powerOfTwo <<= 1) {
20                // Calculate the complement needed to form a power of 2 sum
21                int complement = powerOfTwo - currentDeliciousness;
22              
23                // Add the frequency of the complement to the result
24                // This counts how many previous elements can pair with current element
25                result = (result + frequencyMap.getOrDefault(complement, 0)) % MOD;
26            }
27          
28            // Update the frequency map with the current deliciousness value
29            // If key exists, increment its value by 1; otherwise, set it to 1
30            frequencyMap.merge(currentDeliciousness, 1, Integer::sum);
31        }
32      
33        return result;
34    }
35}
36

1class Solution {
2public:
3    // Define modulo constant for preventing integer overflow
4    const int MOD = 1e9 + 7;
5
6    int countPairs(vector<int>& deliciousness) {
7        // Find the maximum possible sum by doubling the largest element
8        // This sets the upper bound for power of two sums to check
9        int maxSum = *max_element(deliciousness.begin(), deliciousness.end()) << 1;
10      
11        // Hash map to store frequency of each deliciousness value encountered so far
12        unordered_map<int, int> frequencyMap;
13      
14        // Initialize result counter for valid pairs
15        int result = 0;
16      
17        // Iterate through each element in the deliciousness array
18        for (auto& currentValue : deliciousness) {
19            // Check all possible powers of 2 up to maxSum
20            for (int powerOfTwo = 1; powerOfTwo <= maxSum; powerOfTwo <<= 1) {
21                // Calculate the complement needed to form a power of 2 sum
22                int complement = powerOfTwo - currentValue;
23              
24                // Add count of complements found so far to result
25                // Use modulo to prevent overflow
26                result = (result + frequencyMap[complement]) % MOD;
27            }
28          
29            // Increment frequency count for current value
30            // This ensures we only count pairs with elements before current position
31            ++frequencyMap[currentValue];
32        }
33      
34        return result;
35    }
36};
37

1// Define modulo constant for preventing integer overflow
2const MOD = 1e9 + 7;
3
4function countPairs(deliciousness: number[]): number {
5    // Find the maximum possible sum by doubling the largest element
6    // This sets the upper bound for power of two sums to check
7    const maxSum = Math.max(...deliciousness) << 1;
8  
9    // Hash map to store frequency of each deliciousness value encountered so far
10    const frequencyMap: Map<number, number> = new Map();
11  
12    // Initialize result counter for valid pairs
13    let result = 0;
14  
15    // Iterate through each element in the deliciousness array
16    for (const currentValue of deliciousness) {
17        // Check all possible powers of 2 up to maxSum
18        for (let powerOfTwo = 1; powerOfTwo <= maxSum; powerOfTwo <<= 1) {
19            // Calculate the complement needed to form a power of 2 sum
20            const complement = powerOfTwo - currentValue;
21          
22            // Add count of complements found so far to result
23            // Use modulo to prevent overflow
24            result = (result + (frequencyMap.get(complement) || 0)) % MOD;
25        }
26      
27        // Increment frequency count for current value
28        // This ensures we only count pairs with elements before current position
29        frequencyMap.set(currentValue, (frequencyMap.get(currentValue) || 0) + 1);
30    }
31  
32    return result;
33}
34

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)

Pattern 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]

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

1711. Count Good Meals

Problem Description

How We Pick the Algorithm

Why Hash Table / Counting?

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Counting Pairs Twice

2. Incorrect Maximum Sum Calculation

3. Forgetting Modulo Operation

4. Using Set Instead of Counter

5. Checking Non-Powers of 2

6. Including Negative Complements

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Recommended Readings