[LeetCode] 1711. Count Good Meals

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

This problem is like an enhanced 2sum problem. The only difference is, the 'target' number is not explicitly given.

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        M = 10 ** 9 + 7
        result = 0
        seen = defaultdict(int)
        
        # sort the numbers first
        # for one given number there is no larger number before it.
        deliciousness.sort()
        
        for n in deliciousness:
            # the maximum sum of 'n' is n + n
            # try every power of two less than n + n
            target = 1
            while target <= n + n:
                result += seen[target - n]
                result %= M
                target *= 2
            
            # increase the counter of n
            seen[n] += 1
        
        return result