Count Good Meals solution and explanation
Google
9 more videos on this problem
Leetcode 1711. Count Good MealsFraz · 11:30 · 5K views
Count Good Meals | Leetcode 1711 | Leetcode SolutionEasyLeetcode · 25:32 · 2K views
Leetcode 1711. Count Good Meals | Leetcode Weekly Contest 222 | Map Problem | Two pair sum ApproachINFO DECODER · 6:53 · 1K views
1711. Count Good Meals (Leetcode Medium)Programming Live with Larry · 6:15 · 1K views
1711. Count Good Meals | LEETCODE MEDIUM | HASH MAPScode Explainer · 5:58 · 1K views
Episode 49 | Leetcode | Hindi and English | Count Good MealsLet's Leet · 15:50 · 319 views
COUNT GOOD MEALS | LEETCODE QUESTION | C++ SolutionKashish Agrawal · 12:30 · 286 views
Count Good Meals (LeetCode problem 1711)MCCOMP · 11:04 · 282 views
大壮刷题 - LeetCode 1711. Count Good Meals, Medium difficulty, Hash Table, Combination大壮刷题 · 8:07 · 256 views
Hashing 5. Count Good Meals | AlgoMaster Sheet | Leetcode 1711 |CS FOR ALL · 8:41 · 128 views
The problem
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 <= 1050 <= deliciousness[i] <= 220
Approach overview
Problem Overview: You are given an array deliciousness where each value represents a meal. A pair of meals is considered good if their sum equals a power of two (1, 2, 4, 8, ...). The task is to count how many such pairs exist while avoiding double counting.
Approach 1: HashMap Counting Approach (O(n * log M) time, O(n) space)
The key observation is that valid sums must be powers of two. While iterating through the array, check how many previously seen numbers can combine with the current value to reach any power of two. Store frequencies in a hash map. For each element x, iterate through possible powers of two (for example 2^0 to 2^21) and compute target = power - x. A constant-time hash lookup tells how many times target appeared earlier. This transforms the naive pair search into quick frequency lookups. The algorithm runs in O(n * log M) where M is the maximum sum bound (about 22 powers), effectively linear for constraints. Uses concepts from hash table counting and array traversal.
Approach 2: Two Pointer Method (O(n log n + P*n) time, O(1) extra space)
Sort the array first, then evaluate each possible power-of-two sum separately. For a chosen target sum, place two pointers at the beginning and end of the sorted array. Move pointers inward depending on whether the current sum is smaller or larger than the target. When a match appears, count the pair and adjust pointers carefully to avoid duplicates. Sorting costs O(n log n), and the two-pointer scan runs O(n) for each power-of-two target. This approach works well when you want minimal extra memory and can leverage sorted order with the two pointers technique.
Recommended for interviews: The HashMap counting approach is what interviewers usually expect. It demonstrates that you recognized the power-of-two constraint and converted pair searching into frequency lookups. The two-pointer method shows understanding of sorted array techniques but is less direct for this problem. Explaining the brute-force idea first (checking all pairs) and then optimizing with hashing clearly shows your reasoning process.
Approach 1: HashMap Counting Approach
This approach involves iterating through the list of deliciousness, and for each element, checking if a complementary value, such that their sum is a power of two, exists in a hashmap that tracks the frequency of each previously seen value. The search for complements considers all powers of two up to 2^21, which covers the maximum possible value of the sum given the constraints.
from collections import defaultdict
class Solution:
def countPairs(self, deliciousness):
MOD = 10**9 + 7
power_of_twos = [1 << i for i in range(22)]
countMap = defaultdict(int)
result = 0
for d in deliciousness:
for power in power_of_twos:
complement = power - d
result += countMap[complement]
result %= MOD
countMap[d] += 1
return resultimport java.util.HashMap;
public class Solution {
public int countPairs(int[] deliciousness) {
HashMap<Integer, Integer> map = new HashMap<>();
int MOD = 1000000007;
int[] powersOfTwo = new int[22];
for (int i = 0; i < 22; i++) powersOfTwo[i] = 1 << i;
long result = 0;
for (int d : deliciousness) {
for (int j = 0; j < 22; j++) {
int target = powersOfTwo[j] - d;
if (map.containsKey(target)) {
result += map.get(target);
result %= MOD;
}
}
map.put(d, map.getOrDefault(d, 0) + 1);
}
return (int) result;
}
}#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int countPairs(vector<int>& deliciousness) {
unordered_map<int, int> countMap;
int powersOfTwo[22], MOD = 1000000007;
for (int i = 0; i < 22; i++)
powersOfTwo[i] = 1 << i;
long result = 0;
for (int d : deliciousness) {
for (int j = 0; j < 22; j++) {
int target = powersOfTwo[j] - d;
if (countMap.find(target) != countMap.end()) {
result = (result + countMap[target]) % MOD;
}
}
countMap[d]++;
}
return (int) result;
}
};const MOD = 1000000007;
var countPairs = function(deliciousness) {
const countMap = new Map();
const powersOfTwo = Array.from({length: 22}, (_, i) => 2**i);
let result = 0;
for (let d of deliciousness) {
for (let power of powersOfTwo) {
let complement = power - d;
if (countMap.has(complement)) {
result += countMap.get(complement);
result %= MOD;
}
}
countMap.set(d, (countMap.get(d) || 0) + 1);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int countPairs(int* deliciousness, int deliciousnessSize) {
int powersOfTwo[22];
for (int i = 0; i < 22; i++)
powersOfTwo[i] = 1 << i;
int* countMap = calloc(1 << 21, sizeof(int));
long result = 0;
for (int i = 0; i < deliciousnessSize; i++) {
for (int j = 0; j < 22; j++) {
int target = powersOfTwo[j] - deliciousness[i];
if (target >= 0 && target < (1 << 21)) {
result = (result + countMap[target]) % MOD;
}
}
countMap[deliciousness[i]]++;
}
free(countMap);
return (int) result;
}
int main() {
int deliciousness[] = {1, 3, 5, 7, 9};
int size = sizeof(deliciousness) / sizeof(deliciousness[0]);
printf("%d\n", countPairs(deliciousness, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountPairs(int[] deliciousness) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
int MOD = 1000000007;
int[] powersOfTwo = new int[22];
for (int i = 0; i < 22; i++) powersOfTwo[i] = 1 << i;
long result = 0;
foreach (var d in deliciousness) {
foreach (var power in powersOfTwo) {
int target = power - d;
if (countMap.ContainsKey(target)) {
result += countMap[target];
result %= MOD;
}
}
if (countMap.ContainsKey(d))
countMap[d]++;
else
countMap[d] = 1;
}
return (int)result;
}
}In this Python implementation, a defaultdict is used to store the counts of deliciousness values encountered. For each value, it checks all powers of two for possible complements and updates the count of valid combinations, ensuring each addition is within the modulo constraints. This ensures efficient counting with minimal complexity.
Time Complexity: O(n * 22) = O(n), exploiting the predetermined number of powers.
Space Complexity: O(n), with space dedicated to storing elements in the countMap.
Approach 2: Two Pointer Method
The two-pointer method is a variation employing sorting and a double-pointer or two-pointer technique. It first sorts the array and uses two pointers to find pairs that meet the condition. The two pointers traverse the sorted array to find sums that are powers of two, adjusting according to standard two-pointer techniques to skip duplicates or move towards smaller counterparts when sums exceed the power-of-two targets.
class Solution:
def countPairs(self, deliciousness):
deliciousness.sort()
powers = [1 << i for i in range(22)]
result = 0
MOD = 10**9 + 7
for i in range(len(deliciousness)):
for j in range(i + 1, len(deliciousness)):
sum_val = deliciousness[i] + deliciousness[j]
if sum_val in powers:
result += 1
result %= MOD
return resultimport java.util.Arrays;
public class Solution {
public int countPairs(int[] deliciousness) {
Arrays.sort(deliciousness);
int MOD = 1000000007;
int count = 0;
int[] powers = new int[22];
for (int i = 0; i < 22; i++) powers[i] = 1 << i;
for (int i = 0; i < deliciousness.length; i++) {
for (int j = i + 1; j < deliciousness.length; j++) {
int sum = deliciousness[i] + deliciousness[j];
for (int k = 0; k < powers.length; k++) {
if (sum == powers[k]) {
count = (count + 1) % MOD;
break;
}
}
}
}
return count;
}
}#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int countPairs(vector<int>& deliciousness) {
sort(deliciousness.begin(), deliciousness.end());
int MOD = 1000000007;
int count = 0;
int powers[22];
for (int i = 0; i < 22; i++) powers[i] = 1 << i;
for (int i = 0; i < deliciousness.size(); i++) {
for (int j = i + 1; j < deliciousness.size(); j++) {
int sum = deliciousness[i] + deliciousness[j];
for (int k = 0; k < 22; k++) {
if (sum == powers[k]) {
count = (count + 1) % MOD;
break;
}
}
}
}
return count;
}
};var countPairs = function(deliciousness) {
deliciousness.sort((a, b) => a - b);
const powersOfTwo = Array.from({length: 22}, (_, i) => 2**i);
let result = 0;
const MOD = 1e9 + 7;
for (let i = 0; i < deliciousness.length; i++) {
for (let j = i + 1; j < deliciousness.length; j++) {
let sum = deliciousness[i] + deliciousness[j];
if (powersOfTwo.includes(sum)) {
result += 1;
result %= MOD;
}
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int countPairs(int* deliciousness, int deliciousnessSize) {
qsort(deliciousness, deliciousnessSize, sizeof(int), compare);
int count = 0;
int powers[22];
for (int i = 0; i < 22; i++) powers[i] = 1 << i;
for (int i = 0; i < deliciousnessSize; i++) {
for (int j = i + 1; j < deliciousnessSize; j++) {
int sum = deliciousness[i] + deliciousness[j];
for (int k = 0; k < 22; k++) {
if (sum == powers[k]) {
count++; count %= MOD;
break;
}
}
}
}
return count;
}
int main() {
int deliciousness[] = {1, 3, 5, 7, 9};
int size = sizeof(deliciousness) / sizeof(deliciousness[0]);
printf("%d\n", countPairs(deliciousness, size));
return 0;
}using System;
public class Solution {
public int CountPairs(int[] deliciousness) {
Array.Sort(deliciousness);
int MOD = 1000000007;
int count = 0;
int[] powers = new int[22];
for (int i = 0; i < 22; i++) powers[i] = 1 << i;
for (int i = 0; i < deliciousness.Length; i++) {
for (int j = i + 1; j < deliciousness.Length; j++) {
int sum = deliciousness[i] + deliciousness[j];
if (Array.Exists(powers, power => power == sum)) {
count = (count + 1) % MOD;
break;
}
}
}
return count;
}
}In this Python implementation of the two-pointer method, the list soarts first and checks each pair combination for power-of-two sums. While suboptimal due to repeat passes of every combination, it highlights the two-pointer base method, advancing sums comparisons for pairs beyond bruteforce lookup limitations.
Time Complexity: O(n²).
Space Complexity: O(1), ignoring sorting usage beyond input impact.
Approach 3: Hash Table + Enumeration of Powers of Two
According to the problem, we need to count the number of combinations in the array where the sum of two numbers is a power of 2. Directly enumerating all combinations has a time complexity of O(n^2), which will definitely time out.
We can traverse the array and use a hash table cnt to maintain the number of occurrences of each element d in the array.
For each element, we enumerate the powers of two s as the sum of two numbers from small to large, and add the number of occurrences of s - d in the hash table to the answer. Then increase the number of occurrences of the current element d by one.
After the traversal ends, return the answer.
The time complexity is O(n times log M), where n is the length of the array deliciousness, and M is the upper limit of the elements. For this problem, the upper limit M=2^{20}.
We can also use a hash table cnt to count the number of occurrences of each element in the array first.
Then enumerate the powers of two s as the sum of two numbers from small to large. For each s, traverse each key-value pair (a, m) in the hash table. If s - a is also in the hash table, and s - a neq a, then add m times cnt[s - a] to the answer; if s - a = a, then add m times (m - 1) to the answer.
Finally, divide the answer by 2, modulo 10^9 + 7, and return.
The time complexity is the same as the method above.
func countPairs(deliciousness []int) (ans int) {
mx := slices.Max(deliciousness) << 1
const mod int = 1e9 + 7
cnt := map[int]int{}
for _, d := range deliciousness {
for s := 1; s <= mx; s <<= 1 {
ans = (ans + cnt[s-d]) % mod
}
cnt[d]++
}
return
}Approach 4: Default Approach
func countPairs(deliciousness []int) (ans int) {
cnt := map[int]int{}
for _, d := range deliciousness {
cnt[d]++
}
const mod int = 1e9 + 7
for i := 0; i < 22; i++ {
s := 1 << i
for a, m := range cnt {
b := s - a
if n, ok := cnt[b]; ok {
if a == b {
ans += m * (m - 1)
} else {
ans += m * n
}
}
}
}
ans >>= 1
return ans % mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap Counting Approach | Time Complexity: O(n * 22) = O(n), exploiting the predetermined number of powers. |
| Two Pointer Method | Time Complexity: O(n²). |
| Hash Table + Enumeration of Powers of Two | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n * log M) | O(n) | General case. Best when you need near-linear performance and fast pair counting. |
| Two Pointer Method (after sorting) | O(n log n + P*n) | O(1) | Useful when memory usage must stay minimal and sorting is acceptable. |
Frequently asked questions
Is Count Good Meals easy or hard?
Count Good Meals is considered a Medium difficulty problem. The main challenge is recognizing that valid sums must be powers of two and using a hash map to count complements efficiently instead of checking every pair.
Count Good Meals Python/Java solution
Most implementations follow the same logic: iterate through the array, test complements for each power of two, and maintain counts in a hash map. Python typically uses a dictionary, Java uses HashMap, and C++ uses unordered_map. Each version maintains O(n) time complexity.
How to solve Count Good Meals in O(n)?
Iterate through the array and maintain a hash map storing counts of previously seen values. For each number x, check all powers of two and compute target = power - x. If the target exists in the map, add its frequency to the answer. Insert x into the map afterward so future elements can pair with it.
What is the best approach for Count Good Meals?
The hash map counting approach is the most efficient and commonly expected solution. While iterating through the array, check complements that would produce a power-of-two sum and track frequencies in a hash map. This reduces pair checking to constant-time lookups and runs in about O(n) time because only ~22 power values need to be checked.
Is Count Good Meals asked at Google/Amazon/Meta?
Problems involving pair sums, hash maps, and power-of-two constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Count Good Meals tests your ability to convert pair search into hash lookups and handle large input efficiently.
What data structure is used in Count Good Meals?
A hash table (hash map) is the core data structure. It stores the frequency of each previously seen number, allowing constant-time lookups when checking complements needed to reach power-of-two sums.
What is the time complexity of Count Good Meals?
The optimal hash map solution runs in O(n * log M) time where M is the maximum possible sum value. Since the number of power-of-two checks is small (around 22), the complexity behaves like O(n) in practice. Space complexity is O(n) due to the frequency map.