Formatted question description: https://leetcode.ca/all/1711.html
1711. Count Good Meals
Level
Medium
Description
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 i-th
item of food, return the number of different good meals you can make from this list modulo 10^9 + 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 <= 10^5
0 <= deliciousness[i] <= 2^20
Solution
Use a map to store each deliciousness’ number of occurrences and maintain the maximum deliciousness. Loop over deliciousness
. For each element, obtain all the elements that are greater than or equal to the current element such that the sum of the current element and the other element is a power of two, and update the number of good meals. Finally, return the number of good meals.
class Solution {
public int countPairs(int[] deliciousness) {
final int MODULO = 1000000007;
Map<Integer, Long> map = new HashMap<Integer, Long>();
int max = 0;
for (int num : deliciousness) {
long count = map.getOrDefault(num, 0L) + 1;
map.put(num, count);
max = Math.max(max, num);
}
long pairs = 0;
Set<Integer> keySet = map.keySet();
for (int num : keySet) {
long count = map.get(num);
if (num > 0 && (num & (num - 1)) == 0)
pairs = (pairs + count * (count - 1) / 2) % MODULO;
int power2 = 1;
while (power2 <= num * 2)
power2 <<= 1;
int upper = num + max;
while (power2 <= upper) {
int complement = power2 - num;
if (map.containsKey(complement)) {
long complementCount = map.get(complement);
pairs = (pairs + count * complementCount) % MODULO;
}
power2 <<= 1;
}
}
return (int) pairs;
}
}