Count Good Meals
The key idea
A good meal is a pair of dishes whose deliciousness sum is a power of two. Since the maximum sum is bounded (2^21), we can precompute all possible powers of two and use a hash map to count complements efficiently.
Problem
A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two (i.e., 1, 2, 4, 8, ...).
You are given an array deliciousness of integers, where each element represents the deliciousness of a food item. Return the number of different good meals you can make from the array. Since the answer may be large, return it modulo 10^9 + 7.
Two meals are considered different if they use different pairs of indices (order does not matter).
Constraints
- 1 <= deliciousness.length <= 10^5
- 0 <= deliciousness[i] <= 2^20
Examples
Input: deliciousness = [1,3,5,7,9]
Output: 4
Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Complexity
Time: O(n * log maxSum) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY