#1711

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Good Meals

Count Good Meals asks you to find pairs of food items with a sum of deliciousness equal to a power of two.

Problem Statement

In this problem, you are given an array of integers representing the deliciousness of food items. A 'good meal' consists of two different food items where their sum of deliciousness is a power of two. You need to return the total number of distinct good meals you can create from the array, modulo 10^9 + 7.

Given that the number of powers of two is limited to at most 21, the problem can be simplified to finding pairs whose sum matches any of these powers of two. Utilize efficient techniques such as array scanning and hash table lookups to identify these pairs and count the valid meals.

Examples

Example 1

Input: deliciousness = [1,3,5,7,9]

Output: 4

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

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

Solution Approach

Array Scanning with Hash Table

Iterate over the array while using a hash table to track the frequency of each deliciousness value. For each item, check if there is another item in the hash table that, when added to the current item, results in a power of two.

Efficient Power of Two Lookup

The sum of any two deliciousness values must be one of the 21 possible powers of two. Precompute these values and use them to quickly check if a valid pair exists during array scanning.

Modulo Operation for Large Numbers

Since the result could be large, use the modulo operation with 10^9 + 7 to prevent overflow and ensure the result is within the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n), where n is the length of the input array. This is due to the array scan and hash table lookups. The space complexity is O(n) because of the space used by the hash table to store the counts of each deliciousness value.

What Interviewers Usually Probe

Candidate should quickly identify that powers of two are a key part of the solution.
Look for the ability to use hash tables efficiently to track counts of deliciousness values.
Candidates should be able to handle the modulo operation to manage large numbers.

Common Pitfalls or Variants

Common pitfalls

Not considering the number of powers of two, leading to unnecessary checks or inefficient algorithms.
Failing to handle large results correctly using the modulo operation.
Not accounting for duplicates in the array and how they affect the pair counting process.

Follow-up variants

Consider variations where the deliciousness values are restricted to a smaller range, reducing the number of powers of two to consider.
Incorporate constraints where the array can contain only non-negative values or only positive integers.
Explore a scenario where the array can contain repeated pairs of the same value, requiring careful handling of counting.

FAQ

How do I efficiently find pairs of items that sum to a power of two?

You can use an array scanning approach with a hash table to track the counts of deliciousness values and check if the sum of each pair matches a power of two.

What is the significance of powers of two in the problem?

The requirement for the sum of two food items' deliciousness to be a power of two significantly reduces the number of possible sums to check, making the problem more manageable.

What is the time complexity of solving Count Good Meals?

The time complexity is O(n), where n is the length of the array. The approach involves scanning the array and performing constant-time hash table lookups.

What is the role of the modulo operation in this problem?

The modulo operation ensures that the result fits within the given constraints, preventing overflow and ensuring the answer is within the range 0 to 10^9 + 7.

How does GhostInterview assist in preparing for this problem?

GhostInterview helps by offering structured guidance on solving Count Good Meals, ensuring efficient array scanning and hash table usage, and managing large number operations with the modulo.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        mod = 10**9 + 7
        mx = max(deliciousness) << 1
        cnt = Counter()
        ans = 0
        for d in deliciousness:
            s = 1
            while s <= mx:
                ans = (ans + cnt[s - d]) % mod
                s <<= 1
            cnt[d] += 1
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        mod = 10**9 + 7
        mx = max(deliciousness) << 1
        cnt = Counter()
        ans = 0
        for d in deliciousness:
            s = 1
            while s <= mx:
                ans = (ans + cnt[s - d]) % mod
                s <<= 1
            cnt[d] += 1
        return ans

Continue Practicing

#1713 minimum operations to make a subsequence #1726 tuple with same product #1695 maximum erasure value