Count Good Meals

Med

#1568Time: O(N^2), where N is the length of the `deliciousness` array. The two nested loops result in a quadratic number of pairs to check.Space: O(1), as it only uses a few variables to store loop indices and the count, regardless of the input size.2 companies

Data structures

Array Hash Table

Companies

Swiggy Robinhood

Prompt

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²⁰

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible pair of different food items, calculating the sum of their deliciousness, and verifying if that sum is a power of two.

Algorithm

Initialize a counter count to 0.
Initialize MOD = 1_000_000_007.
Use a nested loop to iterate through all pairs of indices (i, j) such that i < j.
For each pair, calculate the sum s = deliciousness[i] + deliciousness[j].
Check if the sum s is a power of two. A positive integer s is a power of two if and only if s > 0 && (s & (s - 1)) == 0.
If s is a power of two, increment the count.
After the loops complete, return the final count.

Walkthrough

This method uses two nested loops to generate all unique pairs of food items. The outer loop runs from i = 0 to n-2 and the inner loop runs from j = i + 1 to n-1, where n is the number of food items. This ensures that every pair (i, j) is considered exactly once.

For each pair, we compute the sum of their deliciousness values. We then need a way to check if this sum is a power of two. A common and efficient way to do this is using a bitwise trick: a positive integer x is a power of two if and only if the expression (x & (x - 1)) equals zero. If the sum satisfies this condition, we increment a counter.

Finally, after checking all pairs, the total count is returned. Since the result can be large, it should be taken modulo 10^9 + 7, although with this approach, the count variable is unlikely to overflow before the program times out.

1class Solution {2    public int countPairs(int[] deliciousness) {3        int n = deliciousness.length;4        long count = 0;5        int MOD = 1_000_000_007;6 7        for (int i = 0; i < n; i++) {8            for (int j = i + 1; j < n; j++) {9                long sum = (long) deliciousness[i] + deliciousness[j];10                // Check if sum is a power of two11                if (sum > 0 && (sum & (sum - 1)) == 0) {12                    count++;13                }14            }15        }16        return (int) (count % MOD);17    }18}

Complexity

Time

O(N^2), where N is the length of the `deliciousness` array. The two nested loops result in a quadratic number of pairs to check.

Space

O(1), as it only uses a few variables to store loop indices and the count, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space, making it very memory-efficient.

Cons

This approach is very slow due to the nested loops, resulting in a quadratic time complexity.
It will not pass the time limits for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' (TLE) error.

A much more efficient approach utilizes a hash map to optimize the search for pairs. Instead of iterating through all pairs, for each number, we can directly calculate the complement needed to form a power-of-two sum and check if we have seen that complement before.

Algorithm

Initialize a hash map, freqMap, to store the frequency of each deliciousness value.
Initialize a long counter count to 0 and MOD = 1_000_000_007.
Iterate through each number d in the deliciousness array.
For each d, iterate through all possible target powers of two, p, that the sum can form. The maximum sum is 2^20 + 2^20 = 2^21, so we check powers from 2^0 to 2^21.
For each power of two p, calculate the required complement target = p - d.
If freqMap contains the key target, it means we have found freqMap.get(target) numbers that can be paired with the current d. Add this frequency to count.
After checking all powers of two for the current d, update its frequency in freqMap. This makes it available for subsequent elements.
After iterating through all elements, return (int) count % MOD.

Walkthrough

This approach is based on the two-sum problem pattern. We iterate through the deliciousness array, and for each element d, we try to find a partner target such that d + target is a power of two.

We maintain a hash map, freqMap, to keep track of the frequencies of the numbers we have processed so far. When we are at a number d, we iterate through a list of possible powers of two that the sum could equal. The maximum possible sum is 2^20 + 2^20 = 2^21, so we only need to check powers of two from 2^0 up to 2^21 (a total of 22 powers).

For each power of two p, we calculate the needed complement target = p - d. We then check our freqMap for the existence of this target. If it exists, we add its frequency (the value in the map) to our total count of good meals. This is because every occurrence of target we've seen so far can form a good meal with the current d.

After checking all possible powers of two for the current number d, we update its own frequency in the freqMap. This single-pass process ensures that we count each pair (i, j) with i != j exactly once and avoids double counting.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int countPairs(int[] deliciousness) {6        int MOD = 1_000_000_007;7        Map<Integer, Integer> freqMap = new HashMap<>();8        long count = 0;9 10        for (int d : deliciousness) {11            for (int i = 0; i <= 21; i++) {12                int powerOfTwo = 1 << i;13                int target = powerOfTwo - d;14 15                if (freqMap.containsKey(target)) {16                    count += freqMap.get(target);17                }18            }19            // It's important to apply modulo after additions to prevent overflow, 20            // though here we do it at the end for simplicity as intermediate count fits long.21            // A safer way is count %= MOD after each addition.22            freqMap.put(d, freqMap.getOrDefault(d, 0) + 1);23        }24 25        return (int) (count % MOD);26    }27}

Complexity

Time

O(N * K), where N is the number of food items and K is the number of powers of two to check. Since K is a small constant (22), the time complexity is effectively linear, O(N).

Space

O(U), where U is the number of unique elements in the `deliciousness` array. In the worst-case scenario where all elements are distinct, the space complexity is O(N).

Trade-offs

Pros

Significantly more efficient than the brute-force approach, with a linear time complexity.
Passes the time limits for the given constraints.
Elegantly handles duplicate values and avoids double-counting pairs.

Cons

Requires extra space to store the frequency map, which can be up to O(N) in the worst case where all elements are unique.

Solutions

Solution

1class Solution:2    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

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4public5  int countPairs(int[] deliciousness) {6    int mx = Arrays.stream(deliciousness).max().getAsInt() << 1;7    int ans = 0;8    Map<Integer, Integer> cnt = new HashMap<>();9    for (int d : deliciousness) {10      for (int s = 1; s <= mx; s <<= 1) {11        ans = (ans + cnt.getOrDefault(s - d, 0)) % MOD;12      }13      cnt.merge(d, 1, Integer : : sum);14    }15    return ans;16  }17}

1class Solution {2public:3  const int mod = 1e9 + 7;4  int countPairs(vector<int> &deliciousness) {5    int mx = *max_element(deliciousness.begin(), deliciousness.end()) << 1;6    unordered_map<int, int> cnt;7    int ans = 0;8    for (auto &d : deliciousness) {9      for (int s = 1; s <= mx; s <<= 1) {10        ans = (ans + cnt[s - d]) % mod;11      }12      ++cnt[d];13    }14    return ans;15  }16};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem