1711-count-good-meals

Try it on leetcode

Description

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i​​​​​​th​​​​​​​​ item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

 

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

 

Constraints:

• 1 <= deliciousness.length <= 105
• 0 <= deliciousness[i] <= 220

Solution(Python)

class Solution:
    def __init__(self):
        self.mod = (10**9) + 7
        self.targets = [2**i for i in range(22)]

    def countPairs(self, deliciousness: List[int]) -> int:
        return self.hashing(deliciousness)

    # Time Complexity: O(n^2)
    # space Complexity: O(1)
    def bruteforce(self, deliciousness: List[int]) -> int:
        n = len(deliciousness)
        cnt = 0

        for i in range(n):
            for j in range(i + 1, n):
                target = deliciousness[i] + deliciousness[j]
                if self.isPowerOfTwo(target):
                    cnt = cnt % self.mod + 1

        return cnt % self.mod

    def isPowerOfTwo(self, x):
        return x != 0 and not (x & x - 1)

    # Time Complexity: O(n)
    # space Complexity: O(n)
    def hashing(self, deliciousness: List[int]) -> int:
        n = len(deliciousness)
        cnt = 0
        FreqhashTable = defaultdict(int)

        for i in range(n):
            for target in self.targets:
                exp_deliciousness = target - deliciousness[i]
                if exp_deliciousness in FreqhashTable:
                    cnt += FreqhashTable[exp_deliciousness]
            FreqhashTable[deliciousness[i]] += 1

        return cnt % self.mod