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 <= 105
0 <= deliciousness[i] <= 220
Solution: Hashtable
Same idea as LeetCode 1: Two Sum
Use a hashtable to store the occurrences of all the numbers added so far. For a new number x, check all possible 2^i – x. ans += freq[2^i – x] 0 <= i <= 21
Time complexity: O(22n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int countPairs(vector<int>& A) { constexpr int kMod = 1e9 + 7; unordered_map<int, int> m; long ans = 0; for (int x : A) { for (int t = 1; t <= 1 << 21; t *= 2) { auto it = m.find(t - x); if (it != end(m)) ans += it->second; } ++m[x]; } return ans % kMod; } }; |
Python3
1 2 3 4 5 6 7 8 9 10 |
class Solution: def countPairs(self, deliciousness: List[int]) -> int: sums = [1<<i for i in range(22)] m = defaultdict(int) ans = 0 for x in deliciousness: for t in sums: if t - x in m: ans += m[t - x] m[x] += 1 return ans % (10**9 + 7) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment