Skip to main content
Talentd

Count Good Meals - Solution & Explanation

MediumArrayHash Table22 min readAsked at: Amazon, Robinhood, Google +1
Practice this problem

Problem Statement

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 i​​​​​​th​​​​​​​​ 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

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.

This C implementation uses an array to function as a hashmap due to the constraint that values can be as high as 2^20. For each deliciousness value, it checks against all powers of two to see if its complement (which forms a power of two when added) exists in the hashmap. The result is accumulated with each such valid pair satisfying the condition. Finally, it returns the count modulo 10^9 + 7.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of the deliciousness array and m is the number of powers of two (22 in this case).
Space Complexity: O(1 << 21) = O(2^21), dedicated to the hashmap.

Try this approach in the editor →

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.

This solution in C uses a two-pointer technique after sorting the array. Although this solution is simple, it's less efficient as it doesn’t optimally reduce pairs via skipping for duplicates or excess sums efficiently, iterating over all pairs between two pointers. Counts only valid power-of-two pairs within the sorted list.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n²). Space Complexity: O(1), aside from input-related space.

Try this approach in the editor →

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
HashMap Counting Approach

Time Complexity: O(n * m), where n is the length of the deliciousness array and m is the number of powers of two (22 in this case).
Space Complexity: O(1 << 21) = O(2^21), dedicated to the hashmap.

Two Pointer Method

Time Complexity: O(n²). Space Complexity: O(1), aside from input-related space.

Hash Table + Enumeration of Powers of Two—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap CountingO(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.

Video Solution

Leetcode 1711. Count Good Meals • Fraz • 5,563 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Good Meals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Possible Recipes from Given Supplies

Next

Max Number of K-Sum Pairs