{x}
blog image

Count Good Meals

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 109 + 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 <= 105
  • 0 <= deliciousness[i] <= 220

1711. Count Good Meals

Problem Description

Given an array deliciousness where deliciousness[i] represents the deliciousness of the i-th food item, find the number of "good meals" that can be made. A good meal consists of exactly two different food items whose deliciousness sum is a power of 2. The result should be modulo 109 + 7.

Solution Approach

The naive approach of checking all pairs of food items has a time complexity of O(n2), which is inefficient for large input arrays. A more efficient approach uses a hash table (or dictionary) to count the occurrences of each deliciousness value. Then, for each deliciousness value, we iterate through powers of 2 and check if the complement (power of 2 minus the current deliciousness) exists in the hash table.

Detailed Explanation with Code

The solution iterates through the deliciousness array. For each element d:

  1. Iterate through powers of 2: We check powers of 2 from 1 up to a maximum value (twice the maximum deliciousness value is sufficient).

  2. Check for complement: For each power of 2 (s), we calculate the complement (s - d). If this complement exists in the hash table cnt, we add the number of occurrences of the complement to the ans (total count of good meals).

  3. Update count: After checking all powers of 2 for the current element d, we increment its count in the hash table cnt.

The code below demonstrates this approach in several programming languages:

Python:

from collections import Counter
 
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        mod = 10**9 + 7
        mx = max(deliciousness) << 1  # Twice the maximum deliciousness
        cnt = Counter()
        ans = 0
        for d in deliciousness:
            s = 1
            while s <= mx:
                ans = (ans + cnt[s - d]) % mod
                s <<= 1  # Efficient way to double s
            cnt[d] += 1
        return ans

Java:

import java.util.*;
 
class Solution {
    private static final int MOD = (int) 1e9 + 7;
 
    public int countPairs(int[] deliciousness) {
        int mx = Arrays.stream(deliciousness).max().getAsInt() << 1;
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int d : deliciousness) {
            for (int s = 1; s <= mx; s <<= 1) {
                ans = (ans + cnt.getOrDefault(s - d, 0)) % MOD;
            }
            cnt.put(d, cnt.getOrDefault(d, 0) + 1);
        }
        return ans;
    }
}

C++:

#include <vector>
#include <unordered_map>
#include <algorithm>
 
class Solution {
public:
    int countPairs(std::vector<int>& deliciousness) {
        long long mod = 1e9 + 7;
        int mx = *std::max_element(deliciousness.begin(), deliciousness.end()) << 1;
        std::unordered_map<int, long long> cnt;
        long long ans = 0;
        for (int d : deliciousness) {
            for (int s = 1; s <= mx; s <<= 1) {
                ans = (ans + cnt[s - d]) % mod;
            }
            cnt[d]++;
        }
        return ans;
    }
};

Go:

package main
 
import (
	"fmt"
	"math"
	"sort"
)
 
func countPairs(deliciousness []int) int {
	mod := int(1e9 + 7)
	mx := int(math.Pow(2, math.Ceil(math.Log2(float64(sort.Slice(deliciousness, func(i, j int) bool { return deliciousness[i] < deliciousness[j] })[len(deliciousness)-1])))))
	cnt := map[int]int{}
	ans := 0
	for _, d := range deliciousness {
		for s := 1; s <= mx; s <<= 1 {
			ans = (ans + cnt[s-d]) % mod
		}
		cnt[d]++
	}
	return ans
}
 
func main() {
	fmt.Println(countPairs([]int{1, 3, 5, 7, 9})) // Output: 4
}

Time and Space Complexity

  • Time Complexity: O(n * log(M)), where n is the length of deliciousness and M is the maximum value in deliciousness. This is because we iterate through the array once and for each element, we iterate through at most log2(2M) powers of 2.

  • Space Complexity: O(n) in the worst case, as the hash table cnt could store all unique deliciousness values. The space used by the hash table dominates the space complexity.

This optimized solution avoids the O(n2) complexity of the naive approach, making it suitable for larger input arrays.