Count Good Meals — Solution in Python, Java & C++
Count Good Meals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Good Meals is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
deliciousness[i] is how tasty the i-th dish on the menu is. A good meal is a pair of two different dishes (different indices) whose deliciousness adds up to a power of two (1, 2, 4, 8, ...).
Return the number of good meals, i.e. pairs of indices i < j with deliciousness[i] + deliciousness[j] a power of two. Dishes with equal deliciousness but different indices are different dishes.
Return the count modulo 10^9 + 7.
Example 1
Input: deliciousness = [2,6,1,1]
Output: 2
Explanation: `2 + 6 = 8` and `1 + 1 = 2`.
Example 2
Input: deliciousness = [0,1,0]
Output: 2
Explanation: Each 0 pairs with the 1 to make `1 = 2^0`; `0 + 0` is not a power of two.
Example 3
Input: deliciousness = [4,4,12,4]
Output: 6
Explanation: Three pairs of 4s make 8, and each 4 with 12 makes 16.
Constraints
1 <= deliciousness.length <= 10^50 <= deliciousness[i] <= 2^20
Hints for Count Good Meals
Hint 1
A pair sum is at most
2^21, so there are only 22 powers of two it could equal.Hint 2
For each dish, the partner it needs for power
2^pis exactly2^p - deliciousness[i].Hint 3
Scan left to right with a hash map of counts seen so far; for each dish add the counts of all 22 possible partners, then record the dish.
How to solve Count Good Meals
Instead of checking every pair, check every power of two: for each dish there are only 22 possible target sums, and each fixes the partner's value.
Approach
- Keep
count[value]for dishes already scanned. - For dish
x, forpfrom 0 to 21, addcount[2^p - x]to the answer. - Then increment
count[x]. - Reduce the answer modulo
10^9 + 7.
Why it works
Each good pair i < j is counted exactly once — at j, under the unique power equal to their sum, when dish i is already in the table. Sums never exceed 2^21, so no power is missed.
Complexity
- Time —
O(22 · n) - Space —
O(n)
Pitfalls
- Zero is allowed:
0 + 1 = 1 = 2^0is a good meal, but0 + 0 = 0is not a power of two. - Go up to
2^21— two dishes of2^20sum to2^21. - Count only earlier dishes so a dish never pairs with itself and no pair is counted twice.
Reference solution
Python
from typing import List
def countPairs(deliciousness: List[int]) -> int:
MOD = 10 ** 9 + 7
count = {}
ans = 0
for x in deliciousness:
for p in range(22):
ans += count.get((1 << p) - x, 0)
count[x] = count.get(x, 0) + 1
return ans % MODJava
public static int countPairs(int[] deliciousness) {
final int MOD = 1000000007;
Map<Integer, Integer> count = new HashMap<>();
int ans = 0;
for (int x : deliciousness) {
for (int p = 0; p <= 21; p++) {
Integer c = count.get((1 << p) - x);
if (c != null) ans = (ans + c) % MOD;
}
count.merge(x, 1, Integer::sum);
}
return ans;
}C++
int countPairs(vector<int>& deliciousness) {
const int MOD = 1000000007;
unordered_map<int, int> count;
int ans = 0;
for (int x : deliciousness) {
for (int p = 0; p <= 21; p++) {
auto it = count.find((1 << p) - x);
if (it != count.end()) ans = (ans + it->second) % MOD;
}
count[x]++;
}
return ans;
}JavaScript
var countPairs = function(deliciousness) {
var MOD = 1000000007;
var count = new Map();
var ans = 0;
for (var i = 0; i < deliciousness.length; i++) {
var x = deliciousness[i];
for (var p = 0; p <= 21; p++) {
var c = count.get((1 << p) - x);
if (c !== undefined) ans = (ans + c) % MOD;
}
count.set(x, (count.get(x) || 0) + 1);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets