Skip to content

1711. Count Good Meals 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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