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^50 <= 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;
}
}