1711. Count Good Meals LeetCode Solution

In this guide, you will get 1711. Count Good Meals LeetCode Solution with the best time and space complexity. The solution to Count Good Meals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Count Good Meals solution in C++
  4. Count Good Meals solution in Java
  5. Count Good Meals solution in Python
  6. Additional Resources
1711. Count Good Meals LeetCode Solution image

Problem Statement of 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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)
See also  745. Prefix and Suffix Search LeetCode Solution

1711. Count Good Meals LeetCode Solution in C++

class Solution {
 public:
  int countPairs(vector<int>& deliciousness) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kMaxBit = 20 + 1;
    const int kMaxPower = pow(2, kMaxBit);
    int ans = 0;
    unordered_map<int, int> count;

    for (const int d : deliciousness) {
      for (int power = 1; power <= kMaxPower; power *= 2)
        if (const auto it = count.find(power - d); it != count.cend()) {
          ans += it->second;
          ans %= kMod;
        }
      ++count[d];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1711. Count Good Meals LeetCode Solution in Java

class Solution {
  public int countPairs(int[] deliciousness) {
    final int kMod = 1_000_000_007;
    final int kMaxBit = 20 + 1;
    final int kMaxPower = (int) Math.pow(2, kMaxBit);
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (final int d : deliciousness) {
      for (int power = 1; power <= kMaxPower; power *= 2) {
        ans += count.getOrDefault(power - d, 0);
        ans %= kMod;
      }
      count.merge(d, 1, Integer::sum);
    }

    return ans;
  }
}
// code provided by PROGIEZ

1711. Count Good Meals LeetCode Solution in Python

class Solution:
  def countPairs(self, deliciousness: list[int]) -> int:
    kMod = 10**9 + 7
    kMaxBit = 20 + 1
    ans = 0
    count = collections.Counter()

    for d in deliciousness:
      for i in range(kMaxBit + 1):
        power = 1 << i
        ans += count[power - d]
        ans %= kMod
      count[d] += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: