Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1711.html

1711. Count Good Meals

Level

Medium

Description

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^9 + 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^5
• 0 <= deliciousness[i] <= 2^20

Solution

Use a map to store each deliciousness’ number of occurrences and maintain the maximum deliciousness. Loop over deliciousness. For each element, obtain all the elements that are greater than or equal to the current element such that the sum of the current element and the other element is a power of two, and update the number of good meals. Finally, return the number of good meals.

• Java
• C++
• Python
• Go

• class Solution {
      public int countPairs(int[] deliciousness) {
          final int MODULO = 1000000007;
          Map<Integer, Long> map = new HashMap<Integer, Long>();
          int max = 0;
          for (int num : deliciousness) {
              long count = map.getOrDefault(num, 0L) + 1;
              map.put(num, count);
              max = Math.max(max, num);
          }
          long pairs = 0;
          Set<Integer> keySet = map.keySet();
          for (int num : keySet) {
              long count = map.get(num);
              if (num > 0 && (num & (num - 1)) == 0)
                  pairs = (pairs + count * (count - 1) / 2) % MODULO;
              int power2 = 1;
              while (power2 <= num * 2)
                  power2 <<= 1;
              int upper = num + max;
              while (power2 <= upper) {
                  int complement = power2 - num;
                  if (map.containsKey(complement)) {
                      long complementCount = map.get(complement);
                      pairs = (pairs + count * complementCount) % MODULO;
                  }
                  power2 <<= 1;
              }
          }
          return (int) pairs;
      }
  }
  
  ############
  
  class Solution {
      private static final int MOD = (int) 1e9 + 7;
  
      public int countPairs(int[] deliciousness) {
          Map<Integer, Integer> cnt = new HashMap<>();
          for (int d : deliciousness) {
              cnt.put(d, cnt.getOrDefault(d, 0) + 1);
          }
          long ans = 0;
          for (int i = 0; i < 22; ++i) {
              int s = 1 << i;
              for (var x : cnt.entrySet()) {
                  int a = x.getKey(), m = x.getValue();
                  int b = s - a;
                  if (!cnt.containsKey(b)) {
                      continue;
                  }
                  ans += 1L * m * (a == b ? m - 1 : cnt.get(b));
              }
          }
          ans >>= 1;
          return (int) (ans % MOD);
      }
  }
  

• // OJ: https://leetcode.com/problems/count-good-meals/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      int countPairs(vector<int>& A) {
          long mod = 1e9 + 7, ans = 0;
          unordered_map<int, int> m;
          for (int n : A) m[n]++;
          for (auto &[a, cnt] : m) {
              for (int i = 0; i <= 21; ++i) {
                  long b = (1 << i) - a;
                  if (b < a || m.count(b) == 0) continue;
                  long c = m[b];
                  if (a == b) ans = (ans + (c * (c - 1) / 2) % mod) % mod;
                  else ans = (ans + cnt * c % mod) % mod; 
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def countPairs(self, deliciousness: List[int]) -> int:
          mod = 10**9 + 7
          cnt = Counter(deliciousness)
          ans = 0
          for i in range(22):
              s = 1 << i
              for a, m in cnt.items():
                  if (b := s - a) in cnt:
                      ans += m * (m - 1) if a == b else m * cnt[b]
          return (ans >> 1) % mod
  
  ############
  
  # 1711. Count Good Meals
  # https://leetcode.com/problems/count-good-meals/
  
  class Solution:
      def countPairs(self, arr: List[int]):
          
          M = 10 ** 9 + 7     
          mp = Counter(arr)
          res = 0
  
          for i in range(22):
  
              p = 1 << i
              
              for k in mp:
                  target = p - k
                  if k == target:
                      res += ((mp[k]) * (mp[k]-1)) // 2
                  elif k < target:
                      res += mp[k] * mp[target]
  
                  res %= M
              
          return res % M
  
      def countPairs(self, A: List[int]):
          
          M = 10 ** 9 + 7     
          mp = Counter()
          res = 0
  
          for num in A:
              
              for i in range(22):
                  target = (1 << i) - num
                  
                  if target in mp:
                      res += mp[target]
              
              mp[num] += 1
              
          return res % M
  
  
  
  

• func countPairs(deliciousness []int) (ans int) {
  	cnt := map[int]int{}
  	for _, d := range deliciousness {
  		cnt[d]++
  	}
  	const mod int = 1e9 + 7
  	for i := 0; i < 22; i++ {
  		s := 1 << i
  		for a, m := range cnt {
  			b := s - a
  			if n, ok := cnt[b]; ok {
  				if a == b {
  					ans += m * (m - 1)
  				} else {
  					ans += m * n
  				}
  			}
  		}
  	}
  	ans >>= 1
  	return ans % mod
  }
  

All Problems

All Solutions