Problem statement

https://leetcode.com/problems/count-good-meals/

Solution

The idea is that sum is not more than 2^22, so for each value dl we can try to find at most 22 pairs. First we use counters and then we calculate number of options. Also take into account the case of equal values.

Complexity

Time complexity is O(n*log M), where n = len(D) and M = 2^22. Space complexity is O(n) to keep counter.

Code

class Solution:
    def countPairs(self, D):
        cnt, ans = Counter(D), 0
        
        for dl in cnt:
            for i in range(22):
                if (1<<i) - dl in cnt and dl * 2 < (1<<i):
                    ans += cnt[dl]*cnt[(1<<i) - dl]
            if dl & (dl-1) == 0 and dl > 0:
                ans += cnt[dl]*(cnt[dl] - 1)//2
            
        return ans % (10**9 + 7)