Count Good Meals
Count Good Meals is a medium arrays & hashing problem solved with the two sum pattern.
The best approach, optimal (hash map, one lookup per power of two), runs in O(22 · n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every pair) up.
Problem
A good meal is a pair of two different dishes whose deliciousness values add up to a power of two (1, 2, 4, 8, ...).
You get an array deliciousness where deliciousness[i] is the value of dish i. Count how many good meals you can form. Two meals are different if they use a different pair of indices, even when the values are the same.
The count can be large, so return it modulo 10^9 + 7.
Examples
Example 1
- Input
deliciousness = [1, 3, 5, 7, 9]- Output
4- Why
- The good pairs are 1 + 3 = 4, 1 + 7 = 8, 3 + 5 = 8 and 7 + 9 = 16.
Example 2
- Input
deliciousness = [0, 0, 4, 4, 4]- Output
9- Why
- Each 0 pairs with each 4 (sum 4): 6 pairs. The three 4s give 3 pairs with sum 8. The two 0s sum to 0, which is not a power of two.
Constraints
1 <= deliciousness.length <= 10^50 <= deliciousness[i] <= 2^20- Return the count modulo
10^9 + 7.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check every pair) | O(n²) | O(1) |
| Optimal (hash map, one lookup per power of two) | O(22 · n) | O(n) |
1Brute force (check every pair)
O(n²)n(n - 1) / 2 pairs, each checked in O(1).O(1)Only a counter.Try every pair i < j and test whether the sum is a power of two: a positive s is a power of two exactly when s & (s - 1) == 0.
- Loop over all pairs i < j.
- Let s = d[i] + d[j]; count it if s > 0 and s & (s - 1) == 0.
- Return the count modulo 10^9 + 7.
class Solution {
public int countPairs(int[] deliciousness) {
int n = deliciousness.length;
long count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int s = deliciousness[i] + deliciousness[j];
if (s > 0 && (s & (s - 1)) == 0) count++;
}
}
return (int) (count % 1_000_000_007L);
}
}class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
n = len(deliciousness)
count = 0
for i in range(n):
for j in range(i + 1, n):
s = deliciousness[i] + deliciousness[j]
if s > 0 and s & (s - 1) == 0:
count += 1
return count % 1_000_000_007class Solution {
public:
int countPairs(vector<int>& deliciousness) {
int n = deliciousness.size();
long long count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int s = deliciousness[i] + deliciousness[j];
if (s > 0 && (s & (s - 1)) == 0) count++;
}
}
return (int) (count % 1000000007LL);
}
};function countPairs(deliciousness) {
const n = deliciousness.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const s = deliciousness[i] + deliciousness[j];
if (s > 0 && (s & (s - 1)) === 0) count++;
}
}
return count % 1000000007;
}2Optimal (hash map, one lookup per power of two)
O(22 · n)22 hash lookups per dish.O(n)The map holds up to n distinct values.Walk the array once, keeping a map from value to how many times it has appeared so far. For the current dish x, every earlier dish equal to 2^p - x makes a good pair, for each of the 22 powers 2^0 ... 2^21. Add those counts, then record x. Counting only earlier dishes makes each pair count once.
- Create an empty map value -> count and a 64-bit total.
- For each dish x: for p from 0 to 21, add count[(1 << p) - x] (0 if absent).
- Then increment count[x].
- Return total modulo 10^9 + 7.
class Solution {
public int countPairs(int[] deliciousness) {
Map<Integer, Integer> seen = new HashMap<>();
long total = 0;
for (int x : deliciousness) {
for (int p = 0; p <= 21; p++) {
total += seen.getOrDefault((1 << p) - x, 0);
}
seen.merge(x, 1, Integer::sum);
}
return (int) (total % 1_000_000_007L);
}
}class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
seen = defaultdict(int)
total = 0
for x in deliciousness:
for p in range(22):
total += seen.get((1 << p) - x, 0)
seen[x] += 1
return total % 1_000_000_007class Solution {
public:
int countPairs(vector<int>& deliciousness) {
unordered_map<int, int> seen;
long long total = 0;
for (int x : deliciousness) {
for (int p = 0; p <= 21; p++) {
auto it = seen.find((1 << p) - x);
if (it != seen.end()) total += it->second;
}
seen[x]++;
}
return (int) (total % 1000000007LL);
}
};function countPairs(deliciousness) {
const seen = new Map();
let total = 0;
for (const x of deliciousness) {
for (let p = 0; p <= 21; p++) {
total += seen.get((1 << p) - x) || 0;
}
seen.set(x, (seen.get(x) || 0) + 1);
}
return total % 1000000007;
}Edge cases to test
- A single dish: no pairs, the answer is 0
- Zeros: 0 + 0 = 0 is not a power of two, but 0 + 1 = 1 is (2^0)
- Many equal values, such as all 1s, where the count exceeds 32-bit range before the modulo
- Two dishes of 2^20, whose sum 2^21 is still a power of two
Hints
Hint 1
The largest possible sum is 2^20 + 2^20 = 2^21, so there are only 22 powers of two a pair can hit.
Hint 2
For a dish x and a power p, the partner must be exactly p - x. This is the two-sum idea repeated for each power.
Hint 3
Scan left to right with a count map of the dishes seen so far, and for each dish add the counts of all 22 possible partners.
FAQ
What is the best time complexity for Count Good Meals?
Optimal (hash map, one lookup per power of two) runs in O(22 · n) time and O(n) extra space. 22 hash lookups per dish.
Which pattern does Count Good Meals use?
It is a arrays & hashing problem that uses the two sum pattern. Other problems with the same pattern: Two Sum, 3Sum.
Is there a brute force solution for Count Good Meals?
Yes. Brute force (check every pair) takes O(n²) time and O(1) space. Try every pair i < j and test whether the sum is a power of two: a positive s is a power of two exactly when s & (s - 1) == 0.
Which edge cases should I test for Count Good Meals?
A single dish: no pairs, the answer is 0; Zeros: 0 + 0 = 0 is not a power of two, but 0 + 1 = 1 is (2^0); Many equal values, such as all 1s, where the count exceeds 32-bit range before the modulo; Two dishes of 2^20, whose sum 2^21 is still a power of two.