Untitled
raw download clone
TEXT
views 32
,
size 1077 b
class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        MOD = 10 ** 9 + 7
        if len(deliciousness) < 2:
            return 0
        
        # Precalculate power of two
        # This step can be reduce, but keep it will be easier to understand
        MAX = max(deliciousness)
        powerOfTwo = [1]
        while powerOfTwo[-1] <= MAX:
            powerOfTwo.append(2 * powerOfTwo[-1])
            
        freq = collections.Counter(deliciousness)

        ans = 0
        for key in freq:
            for number in powerOfTwo:
                if freq.get(number - key) != None:
                    # If two key is the same, ex: [2, 2, 2] -> 3 * 2 // 2 = 3 happy meal
                    if key == number - key:
                        ans += freq.get(key) * (freq.get(key) - 1) // 2
                    # Two key different, [2,2,3,3,3] -> 2 * 3 = 6 happy meal
                    else:
                        ans += freq.get(key) * freq.get(number - key)
            freq[key] = 0
    
        return ans % MOD
close fullscreen
Login or Register to edit or fork this paste. It's free.