Leetcode 1711. Count Good Meals

Problem Explanation

Given a list of food items with their deliciousness values, the goal is to find and count the number of "good meals" that can be made. A "good meal" is a pair of two different food items whose sum of deliciousness is equal to a power of two. In this problem, we are asked to calculate the total number of different "good meals" that can be made using the provided array of deliciousness, modulo 10^9 + 7.

Example Walkthrough

Let's consider the example provided in the prompt:

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

Possible pairs of food items and their sums of deliciousness:

Pair (1,3) --> sum is 1 + 3 = 4.

Pair (1,7) --> sum is 1 + 7 = 8.

Pair (3,5) --> sum is 3 + 5 = 8.

Pair (7,9) --> sum is 7 + 9 = 16.

The number of pairs whose sum of deliciousness is equal to a power of two is 4. Hence, the output should be 4.

Solution Approach

The solution requires to iterate through each possible pair of food items, find the sum of their deliciousness and check if this sum is a power of two.

To check if a number is a power of two, we can use the following approach:

1. Find the log base 2 of the number.
2. If the obtained value is an integer, then the sum is a power of two.

Algorithm steps:

1. Initialize a counter named good_meals to 0.
2. Iterate through each possible pair of food items.
   1. Calculate the sum of deliciousness of the pair.
   2. Check if the sum is a power of two.
      1. If Yes, increment the good_meals counter.
3. Return the value of good_meals.

Let's implement the solution in Python, Java, JavaScript, C++, and C# languages.

Python Solution

1class Solution:
2    def countGoodMeals(self, deliciousness):
3        good_meals = 0
4        MOD = 10**9 + 7
5        counter = dict()
6        max_sum = 2*max(deliciousness)
7        
8        for value in deliciousness:
9            mask = 1
10            while mask <= max_sum:
11                if mask > value and mask - value in counter:
12                    good_meals += counter[mask - value]
13                    good_meals %= MOD
14                
15                mask *= 2
16            counter[value] = counter.get(value,0) + 1
17        return good_meals

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int countGoodMeals(int[] deliciousness) {
6        int good_meals = 0;
7        int MOD = 1000000007;
8        Map<Integer, Integer> counter = new HashMap<>();
9        int max_sum = 2 * getMaxElement(deliciousness);
10
11        for (int value : deliciousness) {
12            int mask = 1;
13            while (mask <= max_sum) {
14                if (mask > value && counter.containsKey(mask - value)) {
15                    good_meals += counter.get(mask - value);
16                    good_meals %= MOD;
17                }
18                
19                mask *= 2;
20            }
21            counter.put(value, counter.getOrDefault(value, 0) + 1);
22        }
23
24        return good_meals;
25    }
26
27    public int getMaxElement(int[] arr) {
28        int max = arr[0];
29        for (int i = 0; i < arr.length; i++) {
30            if (arr[i] > max)
31                max = arr[i];
32        }
33        return max;
34    }
35}

JavaScript Solution

1class Solution {
2    countGoodMeals(deliciousness) {
3        let good_meals = 0;
4        let MOD = 1000000007;
5        let counter = {};
6        let max_sum = 2 * Math.max(...deliciousness);
7
8        for (let value of deliciousness) {
9            let mask = 1;
10            while (mask <= max_sum) {
11                if (mask > value && counter.hasOwnProperty(mask - value)) {
12                    good_meals += counter[mask - value];
13                    good_meals %= MOD;
14                }
15
16                mask *= 2;
17            }
18            counter[value] = (counter[value] || 0) + 1;
19        }
20
21        return good_meals;
22    }
23}

C++ Solution

1#include <unordered_map>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7    int countGoodMeals(std::vector<int>& deliciousness) {
8        int good_meals = 0;
9        int MOD = 1000000007;
10        std::unordered_map<int, int> counter;
11        int max_sum = 2 * *max_element(deliciousness.begin(), deliciousness.end());
12
13        for (int value : deliciousness) {
14            int mask = 1;
15            while (mask <= max_sum) {
16                if (mask > value && counter.find(mask - value) != counter.end()) {
17                    good_meals += counter[mask - value];
18                    good_meals %= MOD;
19                }
20                
21                mask *= 2;
22            }
23            counter[value]++;
24        }
25
26        return good_meals;
27    }
28};

C# Solution

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int CountGoodMeals(int[] deliciousness) {
6        int good_meals = 0;
7        int MOD = 1000000007;
8        Dictionary<int, int> counter = new Dictionary<int, int>();
9        int max_sum = 2 * GetMaxElement(deliciousness);
10
11        foreach (int value in deliciousness) {
12            int mask = 1;
13            while (mask <= max_sum) {
14                if (mask > value && counter.ContainsKey(mask - value)) {
15                    good_meals += counter[mask - value];
16                    good_meals %= MOD;
17                }
18                
19                mask *= 2;
20            }
21            if (!counter.ContainsKey(value))
22                counter.Add(value, 0);
23            counter[value]++;
24        }
25
26        return good_meals;
27    }
28
29    public int GetMaxElement(int[] arr) {
30        int max = arr[0];
31        foreach (int num in arr) {
32            if (num > max)
33                max = num;
34        }
35        return max;
36    }
37}

We have now implemented the solution in Python, Java, JavaScript, C++, and C# languages, and thus provided a comprehensive range of solutions to the problem.

These solutions follow the same algorithm steps mentioned previously: initializing a counter good_meals, iterating through each possible pair of food items, checking if their sum is a power of two, and incrementing the counter if so. After iterating through all possible pairs, the value of the good_meals counter is returned, giving the total number of "good meals" that can be made using the provided array of deliciousness values, modulo 10^9 + 7.