Jobs

Interviews

Discussions

Count Good Meals

Medium

Robinhood

3 views

Topics:

ArraysTwo Pointers

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 10⁹ + 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 <= 10⁵
0 <= deliciousness[i] <= 2²⁰

Try coding it in LeetCode

Count Good Meals

Medium

Robinhood

3 views

Topics:

ArraysTwo Pointers

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.

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 <= 10⁵
0 <= deliciousness[i] <= 2²⁰

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `deliciousness` array and the range of values within it?
Can the `deliciousness` array contain negative numbers, zero, or null values?
Are we looking for distinct pairs (i.e., i != j), or can a number be paired with itself?
If no pairs sum to a power of two, should I return 0?
Since the problem asks for the result modulo 10^9 + 7, can I assume that intermediate calculations won't overflow before applying the modulo operator?

Brute Force Solution

Approach

The brute force way to count good meals is to try every possible pair of food items. We check if each pair sums up to a power of two. If it does, we count it as a good meal.

Here's how the algorithm would work step-by-step:

Take the first food item from the list.
Pair this first item with every other food item in the list, one at a time.
For each pair, calculate the sum of their values.
Check if the sum is a power of two (like 2, 4, 8, 16, etc.).
If the sum is a power of two, then increase the good meal count.
Move to the second food item in the original list.
Pair this second item with every other item (including the first), one at a time.
Repeat the sum and power of two check, and update the good meal count accordingly.
Keep doing this process for every food item in the list, pairing it with all the other items.
Once you've checked all possible pairs, the final good meal count is your answer.

Code Implementation

def count_good_meals_brute_force(food_items):
    number_of_food_items = len(food_items)
    good_meal_count = 0

    for first_food_index in range(number_of_food_items):
        for second_food_index in range(number_of_food_items):
            # Calculate the sum of the two food items.
            food_sum = food_items[first_food_index] + food_items[second_food_index]

            power_of_two = 1

            # We must check if food_sum is a power of 2.
            while power_of_two < food_sum:
                power_of_two *= 2

            if power_of_two == food_sum:
                #We found a good meal; increment the count
                good_meal_count += 1

    # Divide by two as each meal is counted twice
    return good_meal_count // 2

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through each of the n food items. For each food item, it compares it to every other food item in the array to check if their sum is a power of two. This pairing process involves roughly n comparisons for each of the n food items. Therefore, the total number of operations scales proportionally to n multiplied by n. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach iterates through the input list using nested loops, pairing each food item with every other item. It only uses a few integer variables to store indices, sums, and the good meal count. The space used by these variables remains constant regardless of the size of the input list (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to efficiently find pairs of numbers that add up to a power of two. Instead of checking every single pair, we use a technique that dramatically reduces the number of checks needed. We use a way to quickly count how many numbers would complete a power of two when paired with each number in the list.

Here's how the algorithm would work step-by-step:

Think about what a 'good meal' is: two food items whose deliciousness values add up to a power of two (like 2, 4, 8, 16, etc.).
Instead of directly comparing every pair of deliciousness values, consider this: for each food item, figure out what value it needs to be paired with to reach a power of two.
Start with the first food item. Calculate all possible powers of two that it could be part of (e.g., if its deliciousness is 3, consider 4, 8, 16, 32, and so on).
For each power of two you're considering, figure out what the *other* food item's deliciousness would have to be (power of two minus the first food item's deliciousness).
Now, look through the rest of the food items and count how many of them have that *other* required deliciousness value. A fast way to do this is to keep track of how many times each value has appeared.
Add that count to your total number of 'good meals'.
Repeat this process for every food item in the list. Remember that since each pair is counted twice you'll need to handle the duplicate pairs somehow.
Handle edge cases where the two items are the same by counting the duplicate pairs only once.
Once you have the total count, remember to take the result modulo 10^9 + 7 to get the final answer.

Code Implementation

def count_good_meals(deliciousness):
    number_of_meals = 0
    deliciousness_counts = {}
    modulo_value = 10**9 + 7

    for deliciousness_value in deliciousness:
        deliciousness_counts[deliciousness_value] = deliciousness_counts.get(deliciousness_value, 0) + 1

    for deliciousness_value in deliciousness:
        power_of_two = 1

        #Powers of two must be up to at least twice the maximum deliciousness value.
        for _ in range(22): 
            complement = power_of_two - deliciousness_value

            if complement in deliciousness_counts:

                #Avoid double counting pairs with the same value
                if complement == deliciousness_value:
                    number_of_meals = (number_of_meals + deliciousness_counts[complement] - 1) % modulo_value
                else:
                    number_of_meals = (number_of_meals + deliciousness_counts[complement]) % modulo_value
            power_of_two *= 2

    # Divide result by two because each pair was counted twice
    return (number_of_meals // 2) % modulo_value

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through each of the n deliciousness values. Inside the loop, we iterate through a fixed number of possible powers of two, up to a predefined limit. The count of elements with a certain deliciousness value is looked up in constant time. Therefore, for each of the n elements, we perform a fixed number of constant time operations, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm maintains a count of how many times each deliciousness value has appeared. This count is stored in a hash map or frequency array. In the worst case, all N deliciousness values are distinct, so the hash map will store N key-value pairs. Thus, the auxiliary space used by the hash map is proportional to the input size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty because there are no meals to form pairs.
Input array with only one element	Return 0 since we need at least two meals to form a pair.
Maximum sized input array (e.g., n = 10^5)	The solution should use a time complexity that allows processing of large arrays, such as O(n) or O(n log n), avoiding O(n^2).
Input array with all identical deliciousness values	The hash map must correctly count pairs even when all values are same.
Input array contains very large integers (close to the maximum integer value)	Ensure that the sum of two integers does not cause an integer overflow, potentially using a larger data type (long).
No good meals exist in the input array	The solution should correctly return 0 when no pair sums to a power of two.
Multiple pairs can sum to the same power of two	The solution needs to count all such pairs accurately.
Potential Integer Overflow when summing pairs	Use modulo operator (%) to avoid integer overflow when accumulating the count of good meals.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `deliciousness` array and the range of values within it?
Can the `deliciousness` array contain negative numbers, zero, or null values?
Are we looking for distinct pairs (i.e., i != j), or can a number be paired with itself?
If no pairs sum to a power of two, should I return 0?
Since the problem asks for the result modulo 10^9 + 7, can I assume that intermediate calculations won't overflow before applying the modulo operator?

Brute Force Solution

Approach

The brute force way to count good meals is to try every possible pair of food items. We check if each pair sums up to a power of two. If it does, we count it as a good meal.

Here's how the algorithm would work step-by-step:

Take the first food item from the list.
Pair this first item with every other food item in the list, one at a time.
For each pair, calculate the sum of their values.
Check if the sum is a power of two (like 2, 4, 8, 16, etc.).
If the sum is a power of two, then increase the good meal count.
Move to the second food item in the original list.
Pair this second item with every other item (including the first), one at a time.
Repeat the sum and power of two check, and update the good meal count accordingly.
Keep doing this process for every food item in the list, pairing it with all the other items.
Once you've checked all possible pairs, the final good meal count is your answer.

Code Implementation

def count_good_meals_brute_force(food_items):
    number_of_food_items = len(food_items)
    good_meal_count = 0

    for first_food_index in range(number_of_food_items):
        for second_food_index in range(number_of_food_items):
            # Calculate the sum of the two food items.
            food_sum = food_items[first_food_index] + food_items[second_food_index]

            power_of_two = 1

            # We must check if food_sum is a power of 2.
            while power_of_two < food_sum:
                power_of_two *= 2

            if power_of_two == food_sum:
                #We found a good meal; increment the count
                good_meal_count += 1

    # Divide by two as each meal is counted twice
    return good_meal_count // 2

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think about what a 'good meal' is: two food items whose deliciousness values add up to a power of two (like 2, 4, 8, 16, etc.).
Instead of directly comparing every pair of deliciousness values, consider this: for each food item, figure out what value it needs to be paired with to reach a power of two.
Start with the first food item. Calculate all possible powers of two that it could be part of (e.g., if its deliciousness is 3, consider 4, 8, 16, 32, and so on).
For each power of two you're considering, figure out what the *other* food item's deliciousness would have to be (power of two minus the first food item's deliciousness).
Now, look through the rest of the food items and count how many of them have that *other* required deliciousness value. A fast way to do this is to keep track of how many times each value has appeared.
Add that count to your total number of 'good meals'.
Repeat this process for every food item in the list. Remember that since each pair is counted twice you'll need to handle the duplicate pairs somehow.
Handle edge cases where the two items are the same by counting the duplicate pairs only once.
Once you have the total count, remember to take the result modulo 10^9 + 7 to get the final answer.

Code Implementation

def count_good_meals(deliciousness):
    number_of_meals = 0
    deliciousness_counts = {}
    modulo_value = 10**9 + 7

    for deliciousness_value in deliciousness:
        deliciousness_counts[deliciousness_value] = deliciousness_counts.get(deliciousness_value, 0) + 1

    for deliciousness_value in deliciousness:
        power_of_two = 1

        #Powers of two must be up to at least twice the maximum deliciousness value.
        for _ in range(22): 
            complement = power_of_two - deliciousness_value

            if complement in deliciousness_counts:

                #Avoid double counting pairs with the same value
                if complement == deliciousness_value:
                    number_of_meals = (number_of_meals + deliciousness_counts[complement] - 1) % modulo_value
                else:
                    number_of_meals = (number_of_meals + deliciousness_counts[complement]) % modulo_value
            power_of_two *= 2

    # Divide result by two because each pair was counted twice
    return (number_of_meals // 2) % modulo_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty because there are no meals to form pairs.
Input array with only one element	Return 0 since we need at least two meals to form a pair.
Maximum sized input array (e.g., n = 10^5)	The solution should use a time complexity that allows processing of large arrays, such as O(n) or O(n log n), avoiding O(n^2).
Input array with all identical deliciousness values	The hash map must correctly count pairs even when all values are same.
Input array contains very large integers (close to the maximum integer value)	Ensure that the sum of two integers does not cause an integer overflow, potentially using a larger data type (long).
No good meals exist in the input array	The solution should correctly return 0 when no pair sums to a power of two.
Multiple pairs can sum to the same power of two	The solution needs to count all such pairs accurately.
Potential Integer Overflow when summing pairs	Use modulo operator (%) to avoid integer overflow when accumulating the count of good meals.