#1711

Count Good Meals

expert · 1110 · lc medium +32 · premium · verified · 32.6% accepted · 1,126 likes · top 10%

Description

A good meal consists of exactly two distinct food items whose combined deliciousness equals a power of two. Items at different indices are always distinct.

Given an integer array deliciousness, return the number of good meals modulo 10⁹ + 7.

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.

Code

1

2

3

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int: