How do I efficiently find pairs of items that sum to a power of two?

You can use an array scanning approach with a hash table to track the counts of deliciousness values and check if the sum of each pair matches a power of two.

What is the significance of powers of two in the problem?

The requirement for the sum of two food items' deliciousness to be a power of two significantly reduces the number of possible sums to check, making the problem more manageable.

What is the time complexity of solving Count Good Meals?

The time complexity is O(n), where n is the length of the array. The approach involves scanning the array and performing constant-time hash table lookups.

What is the role of the modulo operation in this problem?

The modulo operation ensures that the result fits within the given constraints, preventing overflow and ensuring the answer is within the range 0 to 10^9 + 7.

How does GhostInterview assist in preparing for this problem?

GhostInterview helps by offering structured guidance on solving Count Good Meals, ensuring efficient array scanning and hash table usage, and managing large number operations with the modulo.

#1711

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

大餐计数

大餐是指恰好包含两道不同餐品的一餐，其美味程度之和等于 2 的幂。你可以搭配任意两道餐品做一顿大餐。给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 …

数组哈希表

题目描述

大餐是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。

你可以搭配任意两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 10⁹ + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

lightbulb

解题思路

方法一：哈希表 + 枚举二的幂

根据题意，我们需要统计数组中两个数的和为 $2$ 的幂的组合数。直接暴力枚举所有的组合数，时间复杂度为 $O(n^2)$ ，肯定会超时。

我们可以遍历数组，用哈希表 $cnt$ 维护数组中每个元素 $d$ 出现的次数。

对于每个元素，我们从小到大枚举二的幂次方 $s$ 作为两数之和，将哈希表中 $s - d$ 出现的次数累加到答案中。然后将当前元素 $d$ 出现的次数加一。

遍历结束后，返回答案即可。

时间复杂度 $O(n\times \log M)$ ，其中 $n$ 是数组 deliciousness 的长度，而 $M$ 是元素的上限，对于本题，上限 $M=2^{20}$ 。

我们也可以先用哈希表 $cnt$ 统计数组中每个元素出现的次数。

然后从小到大枚举二的幂次方 $s$ 作为两数之和，对于每个 $s$ ，遍历哈希表每个键值对 $(a, m)$ ，如果 $s - a$ 也在哈希表中，且 $s - a \neq a$ ，则答案加上 $m \times cnt[s - a]$ ；如果 $s - a = a$ ，则答案加上 $m \times (m - 1)$ 。

最后，将答案除以 $2$ 之后，模 $10^9 + 7$ ，返回即可。

时间复杂度与上面的方法相同。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        mod = 10**9 + 7
        mx = max(deliciousness) << 1
        cnt = Counter()
        ans = 0
        for d in deliciousness:
            s = 1
            while s <= mx:
                ans = (ans + cnt[s - d]) % mod
                s <<= 1
            cnt[d] += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n), where n is the length of the input array. This is due to the array scan and hash table lookups. The space complexity is O(n) because of the space used by the hash table to store the counts of each deliciousness value.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should quickly identify that powers of two are a key part of the solution.
question_mark
Look for the ability to use hash tables efficiently to track counts of deliciousness values.
question_mark
Candidates should be able to handle the modulo operation to manage large numbers.

warning

常见陷阱

外企场景

error
Not considering the number of powers of two, leading to unnecessary checks or inefficient algorithms.
error
Failing to handle large results correctly using the modulo operation.
error
Not accounting for duplicates in the array and how they affect the pair counting process.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where the deliciousness values are restricted to a smaller range, reducing the number of powers of two to consider.
arrow_right_alt
Incorporate constraints where the array can contain only non-negative values or only positive integers.
arrow_right_alt
Explore a scenario where the array can contain repeated pairs of the same value, requiring careful handling of counting.

help

常见问题

外企场景

继续练习

#1713 得到子序列的最少操作次数 #1726 同积元组 #1695 删除子数组的最大得分