# 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& deliciousness) { constexpr int kMod = 1'000'000'007; constexpr int kMaxBit = 20 + 1; const int kMaxPower = pow(2, kMaxBit); int ans = 0; unordered_map 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 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