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 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
The description was taken from https://leetcode.com/problems/count-good-meals/.
#O(N*P) Time, O(N) Space Where N is Food and P is Powers of Two
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
seen, powers = {}, []
output = 0
deliciousness.sort()
for i in range(0, 22):
powers.append(2**i)
for food in deliciousness:
for power in powers:
if food * 2 < power:
break
complement = power - food
if complement in seen:
output += seen[complement]
if food in seen:
seen[food] += 1
else:
seen[food] = 1
return output % (10**9 + 7)We are looking for pairs of numbers that sum to a target value.
This is like the classic Two-Sum problem. Similar to that problem, we can derive a solution by storing each number in a HashMap and utilizing the x+y=z formula, solving for y. This translates to complement = target - value.
What makes this problem more difficult than Two-Sum however is the target variable is undetermined, it is just a power of two.
What we can do is generate each power from the given constraints and plug each power in as the target value then pair values together that way.
We will implement a slight optimization, but this solution should be fairly straightforward.
Let's start by initializing a dictionary for food that we have seen and an array for each possible power.
seen, powers = {}, []
We'll also need an output count for the number of pairs we see.
output = 0
Let's also sort the input array for optimization which will be explained later.
deliciousness.sort()
For each power of two up to the twenty-second, we will append the power to the powers array.
We didn't have to make an array for this, we could just do this calculation within each iteration but this may make the solution cleaner.
for i in range(0, 22):
powers.append(2**i)
For each food in the deliciousness array, we will try to pair it with a previous food where both sum to each current power of two.
for food in deliciousness:
for power in powers:
Here is the previously mentioned optimization.
If the current food times two is less than the current power we are trying to sum it to, then we should break and try the next food.
We sorted the array previously, so the current value is the maximum value we have seen so far through our traversal. That means the maximum pair sum we could possibly have is the current value plus the current value if there are duplicates.
If this is less than the current power, then it is also going to be less than each greater power, so this will help us prune our search.
if food * 2 < power:
break
Otherwise, we will calculate the complement.
complement = power - food
If the complement food has been seen, we will increment the output by however many times we saw that food.
This is because we can create a unique pair between the current food and however many of the complement's food there is.
if complement in seen:
output += seen[complement]
Afterward, we will check if the current food has been seen.
If it has, we will increment its count.
If not, we will initialize the food within the seen dictionary.
if food in seen:
seen[food] += 1
else:
seen[food] = 1
Once we have finished with our pairings, we will return the output modulo the given value within the description.
return output % (10**9 + 7)