BinarySearch 1001 Pair Sums to Power of Two

Problem statement

https://binarysearch.com/problems/Pair-Sums-to-Power-of-Two/

Solution

Equal to Leetcode 1711. Count Good Meals.

Complexity

Time complexity is O(n*log M), where n = len(nums) and M = 200000. Space complexity is O(n) to keep counter.

Code

class Solution:
    def solve(self, nums):
        cnt, ans = Counter(nums), 0
        for i in range(32):
            for x in cnt:
                y = (1 << i) - x
                if x == y:
                    ans += cnt[x]*(cnt[x] - 1)
                elif y in cnt:
                    ans += cnt[x] * cnt[y]

        return ans//2