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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Good Meals

Difficulty: Medium

Problem Description

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two. 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^9 + 7.

Key Insights

  • We need to find pairs of food items such that their deliciousness values sum up to a power of two.
  • Powers of two are numbers in the form of 2^k for non-negative integers k.
  • We can use a hash map (or dictionary) to count occurrences of each deliciousness value.
  • For each deliciousness value, we can calculate possible pairs that sum to each power of two.

Space and Time Complexity

Time Complexity: O(n * log(max(deliciousness)))
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a hash map to count the occurrences of each deliciousness. We then iterate through each unique deliciousness value and check against all possible powers of two that can be formed using that value. For each target power of two, we check if the complementary deliciousness (i.e., target - current) exists in our hash map and count valid pairs. Care must be taken not to double-count pairs and ensure that the two items are different.

Code Solutions

def countGoodMeals(deliciousness):
    MOD = 10**9 + 7
    count = 0
    frequency = {}
    
    # Count frequency of each deliciousness value
    for d in deliciousness:
        frequency[d] = frequency.get(d, 0) + 1
        
    # Generate powers of two up to the maximum possible sum
    powers_of_two = [1 << i for i in range(22)]  # 2^0 to 2^21
    
    # Iterate through each unique deliciousness value
    for d in frequency:
        for power in powers_of_two:
            complement = power - d
            if complement in frequency:
                if complement == d:
                    # If both are the same, choose 2 out of frequency[d]
                    count += (frequency[d] * (frequency[d] - 1) // 2) % MOD
                else:
                    # Count pairs (d, complement)
                    count += (frequency[d] * frequency[complement]) % MOD
                    
    return count % MOD
← Back to All Questions