We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Good Meals

Number: 1830

Difficulty: Medium

Paid? No

Companies: Swiggy, Robinhood

Problem Description

Given an integer array "deliciousness" where each element represents the deliciousness value of a food item, count the number of good meals you can make. A good meal is defined as a combination of two distinct items such that their sum is a power of 2. Return the final count modulo 10^9 + 7.

Key Insights

  • A good meal is formed by two items whose sum equals 2^k for some k; precompute possible power of two values in the valid range.
  • Use a hash table to keep track of frequencies of already seen deliciousness values.
  • For each new food item, compute the required complement for each power of two and check if it exists in the hash table.
  • The order of selection matters only by index, and duplicate values are allowed if indices differ.

Space and Time Complexity

Time Complexity: O(n * log(maxSum)) where n is the number of food items and log(maxSum) is the number of powers of two considered (constant in this context). Space Complexity: O(n) for the hash table (or frequency counter).

Solution

The approach uses a hash map (or dictionary) to maintain the count of previously seen deliciousness values. For each current value, the algorithm iterates through potential power-of-two sums and calculates the required complement (complement = power - current value). If the complement exists in the hash map, it adds the corresponding frequency to the overall count of good meals. Finally, update the hash table with the current value frequency. The modulo operation is applied to prevent overflow. This method avoids a double loop by leveraging the constant number of power values possible (given the constraints).

Code Solutions

# Python solution using a dictionary to count frequencies.
MOD = 10**9 + 7

def countGoodMeals(deliciousness):
    # Precompute all possible powers of 2 that are within the valid sum range.
    max_val = max(deliciousness)
    power = 1
    powers_of_2 = []
    # Since maximum deliciousness can be 2^20, maximum sum can be 2^(21) at most.
    while power <= 2 * max_val:
        powers_of_2.append(power)
        power *= 2
    
    count = 0
    freq = {}
    
    for value in deliciousness:
        # For each potential power of 2, check if complement exists in freq map.
        for p in powers_of_2:
            complement = p - value
            if complement in freq:
                count = (count + freq[complement]) % MOD
        # Update the frequency of the current value.
        freq[value] = freq.get(value, 0) + 1
    
    return count

# Example usage:
# print(countGoodMeals([1,3,5,7,9]))  # Output: 4
← Back to All Questions