1711. Count Good Meals
Problem Description
In this problem, we are given an array called deliciousness
where each element represents the deliciousness level of a specific food item. We are tasked with finding combinations of exactly two different food items such that their total deliciousness equals a power of two. These combinations are called "good meals". To clarify, two food items are considered different if they are at different indices in the array, even if their deliciousness values are identical.
The output should be the number of good meals that we can create from the given list, and because this number could be very large, we are instructed to return it modulo 10^9 + 7
. A modular result is a standard requirement in programming challenges to avoid overflow issues with high numbers.
Intuition
To solve this problem, we can use a hash map (in Python, this is a dictionary) to store the frequency of each deliciousness value. We iterate over all possible powers of two (up to the 21st power since the input constraint is 2^20
), and within this iteration, we check each unique deliciousness value. For each of these values, say a
, we look for another value b
such that a + b
equals the current power of two we're checking against. This value b
must be 2^i - a
.
Here's the step-by-step breakdown of our approach:
- Initialize a
Counter
for the arraydeliciousness
to keep track of the number of occurrences of each value of deliciousness. - Initialize a variable
ans
to keep track of the total number of good meals. - Loop through all the powers of two up to
2^21
. This covers the range of possible sums of the two deliciousness values. - For each deliciousness value
a
found in the hash map we created, calculateb = 2^i - a
. - If
b
is also in the hash map anda != b
, then we have found a pair of different food items whose deliciousness sums to a power of two.- In this case, we add to
ans
the product of the number of timesa
appears and the number of timesb
appears.
- In this case, we add to
- If
a == b
, we have found a pair of the same food items, and we add toans
the product of the number of timesa
appears withm - 1
because you cannot count the same pair twice. - Since each pair will be counted twice during this process (once for each element as
a
and once asb
), we must divide the total answer by 2 to get the correct count. - Finally, take the modulo of the count by
10^9 + 7
to get our answer within the required range.
It is important to note that we use a bit manipulation trickā1 << i
āto quickly find the i-th power of two, which greatly reduces the time complexity.
Solution Approach
The implementation uses a Counter
from the Python collections
module, which is essentially a hash map or dictionary designed to count the occurrences of each element in an iterable. This data structure is ideal for keeping track of the frequency of deliciousness in the given deliciousness
array.
Here's a step-by-step guide to how the algorithm and data structures are used in the solution:
-
First, a
Counter
object namedcnt
is created to store the frequency of each value of deliciousness from the array. -
We set
ans
to 0 as an accumulator for the total number of good meals. -
We loop through all possible powers of two up to
2^21
(specified as22
in therange(22)
because range goes up to but does not include the end value in Python). We need to cover2^20
since it's the maximum sum according to the problem constraints regarding deliciousness. -
Inside this loop, we calculate
s = 1 << i
, which is a bit manipulation operation that left-shifts the number 1 byi
places, effectively calculating2^i
. -
With each power of two, we iterate over the items in the
Counter
object, wherea
is a deliciousness value from the array, andm
is its frequency (the number of times it appears). -
We then calculate
b = s - a
, to find the complementary deliciousness value that would make a sum ofs
witha
. -
We check if
b
is present in ourCounter
. If it is, we have a potential good meal. However, we must be mindful of counting pairs correctly:-
If
a
equalsb
, then we incrementans
bym * (m - 1)
because we can't use the same item twice, hence we consider the combinations without repetition. -
If
a
does not equalb
, then we incrementans
bym * cnt[b]
, considering all combinations between the occurrences ofa
andb
.
-
-
After the loop, since every pair is counted twice (once for each of its two items, as both
a
andb
), we divideans
by 2 to obtain the actual number of good meals. -
Lastly, we apply modulo
10^9 + 7
to our result to handle the large numbers and prevent integer overflow issues as per the problem's requirement.
By utilizing a hash map (Counter) and iterating over the powers of two, the solution effectively pairs up food items while avoiding nested loops that would significantly increase the time complexity. This allows for an efficient solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the array deliciousness = [1, 3, 5, 7, 9]
.
-
We first create a
Counter
object from thedeliciousness
array, which will count the frequency of each value. In this case, all values are unique and appear once, so our counter (cnt
) would look like this:{1:1, 3:1, 5:1, 7:1, 9:1}
. -
We initialize
ans
to 0 to begin counting the number of good meals. -
Now, we loop through all possible powers of two up to
2^21
. For simplicity, consider that we just check up to2^3
(or 8) for this example. Our powers of two are therefore[1, 2, 4, 8]
. -
For the power of 2 (say
s = 2^i
), we loop through theCounter
object items. Let's first chooses = 4
and consider the entries in our counter. We havea
as the key andm
as the frequency (always 1 in this case). -
For each
a
, we calculateb = s - a
to find the complementary deliciousness value. -
We check if
b
exists in our counter. If it does, anda
is not equal tob
, then we found a good meal pair and incrementans
by the product of their frequencies (sincem
is always 1, it would just be incremented by 1). -
However, if
a
equalsb
, then we incrementans
bym * (m - 1) / 2
which is zero in this case, as there's only one of each item. -
We continue this process for all powers of two. Given our example and
s = 4
, we notice that pairs(1, 3)
and(3, 1)
form good meals because1+3=4
, which is a power of two. Both pairs are counted separately, soans
is incremented twice. -
At the end of the loop, assuming we found no other pairs for other powers of two,
ans
would be 2 (since we found the(1, 3)
pair twice). We then divide it by 2 to correct for the double counting, leaving us with a finalans
of 1. -
Lastly, we apply modulo
10^9 + 7
to our result. Since ourans
is much less than10^9 + 7
, it remains unchanged.
Our final answer is that there is 1 good meal combination in the deliciousness
array [1, 3, 5, 7, 9]
when considering powers of two up to 2^3
. If we extended it to 2^21
, there may be more combinations available.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def countPairs(self, deliciousness: List[int]) -> int:
5 # Define the modulus for the final answer due to large numbers
6 mod = 10**9 + 7
7
8 # Create a counter to count occurrence of each value in deliciousness
9 count = Counter(deliciousness)
10
11 # Initialize the answer to zero
12 answer = 0
13
14 # Iterate through powers of two from 2^0 to 2^21
15 for i in range(22):
16 power_two_sum = 1 << i # Calculate the power of two for current i
17
18 # Iterate through each unique value in deliciousness
19 for value, frequency in count.items():
20 complement = power_two_sum - value # Find the complement
21
22 # If the complement is also in deliciousness
23 if complement in count:
24
25 # If value and complement are the same, choose pairs from the same number (frequency choose 2)
26 if value == complement:
27 answer += frequency * (frequency - 1) // 2
28 else:
29 # If they are different, we count all unique pairs (frequency_a * frequency_b)
30 answer += frequency * count[complement]
31
32 # Divide by 2 because each pair has been counted twice
33 answer //= 2
34
35 # Return the final answer modulo 10^9 + 7
36 return answer % mod
37
1class Solution {
2 // Define the modulus value for large numbers to avoid overflow
3 private static final int MOD = (int) 1e9 + 7;
4
5 // Method to count the total number of pairs with power of two sums
6 public int countPairs(int[] deliciousness) {
7 // Create a hashmap to store the frequency of each value in the deliciousness array
8 Map<Integer, Integer> frequencyMap = new HashMap<>();
9 for (int value : deliciousness) {
10 frequencyMap.put(value, frequencyMap.getOrDefault(value, 0) + 1);
11 }
12
13 long pairCount = 0; // Initialize the pair counter to 0
14
15 // Loop through each power of 2 up to 2^21 (because 2^21 is the closest power of 2 to 10^9)
16 for (int i = 0; i < 22; ++i) {
17 int sum = 1 << i; // Calculate the sum which is a power of two
18 for (var entry : frequencyMap.entrySet()) {
19 int firstElement = entry.getKey(); // Key in the map is a part of the deliciousness pair
20 int firstCount = entry.getValue(); // Value in the map is the count of that element
21 int secondElement = sum - firstElement; // Find the second element of the pair
22
23 // Check if the second element exists in the map
24 if (!frequencyMap.containsKey(secondElement)) {
25 continue; // If it doesn't, continue to the next iteration
26 }
27
28 // If the second element exists, increment the pair count
29 // If both elements are the same, we must avoid counting the pair twice
30 pairCount += (long) firstCount * (firstElement == secondElement ? firstCount - 1 : frequencyMap.get(secondElement));
31 }
32 }
33
34 // Divide the result by 2 because each pair has been counted twice
35 pairCount >>= 1;
36
37 // Return the result modulo MOD to get the answer within the range
38 return (int) (pairCount % MOD);
39 }
40}
41
1class Solution {
2public:
3 const int MOD = 1e9 + 7;
4
5 int countPairs(vector<int>& deliciousness) {
6 // Create map to store the frequency of each deliciousness value
7 unordered_map<int, int> countMap;
8 // Populate the frequency map
9 for (int& value : deliciousness) {
10 ++countMap[value];
11 }
12 long long totalPairs = 0; // Using long long to prevent overflow
13
14 // Iterate over all possible powers of two up to 2^21
15 for (int i = 0; i < 22; ++i) {
16 int sum = 1 << i; // Current sum target (power of two)
17 // Iterate over the frequency map to check for pairs
18 for (auto& [deliciousValue, frequency] : countMap) {
19 int complement = sum - deliciousValue; // Complement to make a power of two
20 // Check if complement exists in the map
21 if (!countMap.count(complement)) continue;
22 // If it's the same number, pair it with each other (except with itself)
23 // Else multiply frequencies of the two numbers
24 totalPairs += deliciousValue == complement ?
25 static_cast<long long>(frequency) * (frequency - 1) :
26 static_cast<long long>(frequency) * countMap[complement];
27 }
28 }
29
30 totalPairs >>= 1; // Each pair is counted twice, so divide by 2
31 return totalPairs % MOD; // Modulo operation to avoid overflow
32 }
33};
34
1// Define MOD constant for modulus operation to avoid overflow
2const MOD = 1e9 + 7;
3
4// Function to count pairs with sum that are power of two
5function countPairs(deliciousness: number[]): number {
6 // Create map to store the frequency of each deliciousness value
7 const countMap = new Map<number, number>();
8
9 // Populate the frequency map with deliciousness counts
10 for (const value of deliciousness) {
11 const count = countMap.get(value) || 0;
12 countMap.set(value, count + 1);
13 }
14
15 let totalPairs = 0; // Using long to prevent overflow
16
17 // Iterate over all possible powers of two up to 2^21
18 for (let i = 0; i < 22; ++i) {
19 const sum = 1 << i; // Current sum target (power of two)
20
21 // Iterate over the frequency map to check for pairs
22 for (const [deliciousValue, frequency] of countMap.entries()) {
23 const complement = sum - deliciousValue; // Complement to make a power of two
24
25 if (!countMap.has(complement)) continue; // Continue if complement does not exist
26
27 // Calculate the total pairs
28 // If it's the same number, combine it with each other (except with itself)
29 // Else multiply frequencies of the two numbers
30 totalPairs += deliciousValue === complement
31 ? frequency * (frequency - 1)
32 : frequency * (countMap.get(complement) as number);
33 }
34 }
35
36 totalPairs /= 2; // Each pair is counted twice, so divide by 2
37
38 // Return the number of pairs mod MOD to prevent overflow
39 return totalPairs % MOD;
40}
41
Time and Space Complexity
Time Complexity
The provided code has two nested loops. The outer loop is constant, iterating 22 times corresponding to powers of two up to 2^21
, as any pair of meals should have a sum that is a power of two for a maximum possible pair value of 2^(20+20) = 2^40
, and the closest power of two is 2^41
.
The inner loop iterates through every element a
in the deliciousness
list once. So, if n
is the length of deliciousness
, the inner loop has a time complexity of O(n)
.
The if
condition inside the inner loop checks if b
exists in cnt
, which is a Counter
(essentially a dictionary), and this check is O(1)
on average. The increment of ans
is also O(1)
.
So, multiplying the constant 22
by the O(n)
complexity of the inner loop gives the total time complexity:
T(n) = 22 * O(n) = O(n)
Space Complexity
The cnt
variable is a Counter
that stores the occurrences of each item in deliciousness
. At worst, if all elements are unique, cnt
would be the same size as deliciousness
, so the space used by cnt
is O(n)
where n
is the length of deliciousness
.
S(n) = O(n)
There is a negligible additional space used for the loop indices, calculations, and single-item b
, which does not depend on the size of deliciousness
and thus does not affect the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!