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 ith 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 <= 1050 <= deliciousness[i] <= 220Problem Overview: You are given an array deliciousness where each value represents a meal. A pair of meals is considered good if their sum equals a power of two (1, 2, 4, 8, ...). The task is to count how many such pairs exist while avoiding double counting.
Approach 1: HashMap Counting Approach (O(n * log M) time, O(n) space)
The key observation is that valid sums must be powers of two. While iterating through the array, check how many previously seen numbers can combine with the current value to reach any power of two. Store frequencies in a hash map. For each element x, iterate through possible powers of two (for example 2^0 to 2^21) and compute target = power - x. A constant-time hash lookup tells how many times target appeared earlier. This transforms the naive pair search into quick frequency lookups. The algorithm runs in O(n * log M) where M is the maximum sum bound (about 22 powers), effectively linear for constraints. Uses concepts from hash table counting and array traversal.
Approach 2: Two Pointer Method (O(n log n + P*n) time, O(1) extra space)
Sort the array first, then evaluate each possible power-of-two sum separately. For a chosen target sum, place two pointers at the beginning and end of the sorted array. Move pointers inward depending on whether the current sum is smaller or larger than the target. When a match appears, count the pair and adjust pointers carefully to avoid duplicates. Sorting costs O(n log n), and the two-pointer scan runs O(n) for each power-of-two target. This approach works well when you want minimal extra memory and can leverage sorted order with the two pointers technique.
Recommended for interviews: The HashMap counting approach is what interviewers usually expect. It demonstrates that you recognized the power-of-two constraint and converted pair searching into frequency lookups. The two-pointer method shows understanding of sorted array techniques but is less direct for this problem. Explaining the brute-force idea first (checking all pairs) and then optimizing with hashing clearly shows your reasoning process.
This approach involves iterating through the list of deliciousness, and for each element, checking if a complementary value, such that their sum is a power of two, exists in a hashmap that tracks the frequency of each previously seen value. The search for complements considers all powers of two up to 2^21, which covers the maximum possible value of the sum given the constraints.
This C implementation uses an array to function as a hashmap due to the constraint that values can be as high as 2^20. For each deliciousness value, it checks against all powers of two to see if its complement (which forms a power of two when added) exists in the hashmap. The result is accumulated with each such valid pair satisfying the condition. Finally, it returns the count modulo 10^9 + 7.
Time Complexity: O(n * m), where n is the length of the deliciousness array and m is the number of powers of two (22 in this case).
Space Complexity: O(1 << 21) = O(2^21), dedicated to the hashmap.
The two-pointer method is a variation employing sorting and a double-pointer or two-pointer technique. It first sorts the array and uses two pointers to find pairs that meet the condition. The two pointers traverse the sorted array to find sums that are powers of two, adjusting according to standard two-pointer techniques to skip duplicates or move towards smaller counterparts when sums exceed the power-of-two targets.
This solution in C uses a two-pointer technique after sorting the array. Although this solution is simple, it's less efficient as it doesn’t optimally reduce pairs via skipping for duplicates or excess sums efficiently, iterating over all pairs between two pointers. Counts only valid power-of-two pairs within the sorted list.
Time Complexity: O(n²). Space Complexity: O(1), aside from input-related space.
According to the problem, we need to count the number of combinations in the array where the sum of two numbers is a power of 2. Directly enumerating all combinations has a time complexity of O(n^2), which will definitely time out.
We can traverse the array and use a hash table cnt to maintain the number of occurrences of each element d in the array.
For each element, we enumerate the powers of two s as the sum of two numbers from small to large, and add the number of occurrences of s - d in the hash table to the answer. Then increase the number of occurrences of the current element d by one.
After the traversal ends, return the answer.
The time complexity is O(n times log M), where n is the length of the array deliciousness, and M is the upper limit of the elements. For this problem, the upper limit M=2^{20}.
We can also use a hash table cnt to count the number of occurrences of each element in the array first.
Then enumerate the powers of two s as the sum of two numbers from small to large. For each s, traverse each key-value pair (a, m) in the hash table. If s - a is also in the hash table, and s - a neq a, then add m times cnt[s - a] to the answer; if s - a = a, then add m times (m - 1) to the answer.
Finally, divide the answer by 2, modulo 10^9 + 7, and return.
The time complexity is the same as the method above.
| Approach | Complexity |
|---|---|
| HashMap Counting Approach | Time Complexity: O(n * m), where n is the length of the deliciousness array and m is the number of powers of two (22 in this case). |
| Two Pointer Method | Time Complexity: O(n²). Space Complexity: O(1), aside from input-related space. |
| Hash Table + Enumeration of Powers of Two | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n * log M) | O(n) | General case. Best when you need near-linear performance and fast pair counting. |
| Two Pointer Method (after sorting) | O(n log n + P*n) | O(1) | Useful when memory usage must stay minimal and sorting is acceptable. |
Leetcode 1711. Count Good Meals • Fraz • 5,455 views views
Watch 9 more video solutions →Practice Count Good Meals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor