Count Good Meals

Count Good Meals

What is this problem about?

The Count Good Meals interview question defines a "good meal" as a pair of items from a list whose prices sum up to a power of 2 (e.g., 1, 2, 4, 8, ...). Given an array of prices, you need to count how many pairs (i, j) form a good meal. You need to return the result modulo 10^9 + 7.

Why is this asked in interviews?

Swiggy and Robinhood use the Hash Table interview pattern for this problem to test your ability to optimize a "Two Sum" variation. Instead of a single target, you have multiple targets (all powers of 2 up to 2^21). It evaluates if you can efficiently check all potential targets for each element in the array.

Algorithmic pattern used

This is a Two Sum variation using a Hash Map.

1. Iterate through the array.
2. For each price p, iterate through all possible powers of 2 (from 1 to 2^21).
3. Calculate the complement = power_of_2 - p.
4. Look up the frequency of the complement in your Hash Map and add it to the total.
5. Update the frequency of p in the map.

Example explanation

prices = [1, 3, 5]

1. p = 1: No complements in map. Add {1: 1}.
2. p = 3: Target 4. 4 - 3 = 1. 1 is in map! Count += 1. Add {3: 1}.
3. p = 5: Target 8. 8 - 5 = 3. 3 is in map! Count += 1. Add {5: 1}. Total = 2.

Common mistakes candidates make

• O(N * 2^N): Trying to check every pair manually, which is too slow.
• Duplicate Counting: Counting the same pair twice if you don't use the Hash Map correctly during the single pass.
• Power of 2 Range: Not checking a wide enough range of powers. Since prices can be up to 2^20, their sum can be up to 2^21.

Interview preparation tip

Always use a single-pass Hash Map approach for "Pair Sum" problems. By checking the complement against what's already in the map and then adding the current element, you automatically avoid counting a pair twice or counting an element with itself.