What is the primary approach for solving the Range Product Queries of Powers problem?

The primary approach involves using bit manipulation to construct the 'powers' array from the binary representation of n, then using a prefix product array to efficiently answer range product queries.

How do we handle large numbers when solving Range Product Queries of Powers?

To handle large numbers, each product result is computed modulo 10^9 + 7, ensuring that the answers fit within the problem's constraints.

Why is a prefix product array useful in this problem?

A prefix product array allows us to calculate the product of any subarray in constant time, making it much more efficient than recalculating the product for each query.

How do you optimize for large values of n in Range Product Queries of Powers?

Optimizing for large values of n involves efficiently constructing the powers array using the binary representation of n and applying a prefix product array to minimize the number of operations needed for each query.

Can the Range Product Queries of Powers problem be extended to other operations?

Yes, the problem can be adapted to other operations, such as sum or minimum, instead of product within the given range.

#2438

Medium

auto_awesome前缀和

LeetCode 题解工作台

二的幂数组中查询范围内的乘积

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含最少数目的 2 的幂，且它们的和为 n 。 powers 数组是非递减顺序的。根据前面描述，构造 powers 数组的方法是唯一的。同时给你一个下标从 0 开始的二维整数数组 queries ，其中 quer…

数组位运算前缀和

题目描述

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含最少数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [left_i, right_i] ，其中 queries[i] 表示请你求出满足 left_i <= j <= right_i 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10⁹ + 7 取余。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10⁹ + 7 取余得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10⁹ + 7 取余后结果相同，所以返回 [2] 。

提示：

1 <= n <= 10⁹
1 <= queries.length <= 10⁵
0 <= start_i <= end_i < powers.length

lightbulb

解题思路

方法一：位运算 + 模拟

我们可以使用位运算（Lowbit）来得到 $\textit{powers}$ 数组，然后通过模拟的方式求出每个查询的答案。

首先，对于给定的正整数 $n$ ，我们通过 $n \& -n$ 可以快速得到二进制表示中最低位的 $1$ 对应的数值，也就是当前数的最小 $2$ 的幂因子。对 $n$ 反复执行这个操作并减去该值，就能依次得到所有置位的 $2$ 的幂，形成 $\textit{powers}$ 数组。这个数组是递增的，且长度等于 $n$ 的二进制表示中 $1$ 的个数。

接下来，我们需要处理每个查询。对于当前查询 $(l, r)$ ，我们需要计算

\textit{answers}[i] = \prod_{j=l}^{r} \textit{powers}[j]

其中 $\textit{answers}[i]$ 是第 $i$ 个查询的答案。由于查询的结果可能非常大，我们需要对每个答案取模 $10^9 + 7$ 。

时间复杂度 $O(m \times \log n)$ ，其中 $m$ 为数组 $\textit{queries}$ 的长度。忽略答案的空间消耗，空间复杂度 $O(\log n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        powers = []
        while n:
            x = n & -n
            powers.append(x)
            n -= x
        mod = 10**9 + 7
        ans = []
        for l, r in queries:
            x = 1
            for i in range(l, r + 1):
                x = x * powers[i] % mod
            ans.append(x)
        return ans

speed

复杂度分析

指标	值
时间	O(\log^2 n + q)
空间	O(\log^2 n)

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate effectively apply bit manipulation to derive the powers array?
question_mark
Can the candidate explain the trade-offs between using a brute force solution and an optimized approach with prefix products?
question_mark
How well does the candidate handle large query sets and large values of n in terms of both time and space complexity?

warning

常见陷阱

外企场景

error
Not using modular arithmetic during product calculations, leading to overflow errors.
error
Inefficiently recalculating products for each query instead of utilizing a prefix product array.
error
Failing to optimize for the constraints, particularly when handling a large number of queries or large values of n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be generalized to other operations like sum or minimum instead of product within a given range.
arrow_right_alt
Instead of answering multiple queries, solve for a single query at a time in an optimized manner using bit manipulation.
arrow_right_alt
Extend the problem to handle negative values of n by adjusting the binary representation approach.

help

常见问题

外企场景

继续练习

#2588 统计美丽子数组数目 #2680 最大或值 #1829 每个查询的最大异或值