Watch 10 video solutions for Count Good Meals, a medium level problem involving Array, Hash Table. This walkthrough by Fraz has 5,455 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |