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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

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

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

请你返回一个数组 _ _answers ，长度与 _ _queries 的长度相同，其中 _ _answers[i]是第 _ _i
个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 109 + 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 。
每个答案对 109 + 7 得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

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

提示：

  • 1 <= n <= 109
  • 1 <= queries.length <= 105
  • 0 <= starti <= endi < powers.length

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

方法一：暴力

拆分 n，把二的幂次记到一个数组 a 中，对每个询问，直接遍历 a。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
MOD = 10 ** 9 + 7

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        a = []
        while n:
            lb = n & -n
            a.append(lb)
            n ^= lb
        return [reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const mod int = 1e9 + 7

func productQueries(n int, queries [][]int) []int {
	a := []int{}
	for n > 0 {
		lb := n & -n
		a = append(a, lb)
		n ^= lb
	}
	ans := make([]int, len(queries))
	for i, q := range queries {
		mul := 1
		for _, x := range a[q[0] : q[1]+1] {
			mul = mul * x % mod
		}
		ans[i] = mul
	}
	return ans
}

复杂度分析

  • 时间复杂度：O(m\log n)，其中 m 为 queries 的长度。
  • 空间复杂度：O(\log n)。返回值不计入。

方法二：预处理

注意到 a 的长度很小，我们可以直接预处理所有询问。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MOD = 10 ** 9 + 7

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        a = []
        while n:
            lb = n & -n
            a.append(lb)
            n ^= lb
        na = len(a)
        res = [[0] * na for _ in range(na)]
        for i, x in enumerate(a):
            res[i][i] = x
            for j in range(i + 1, na):
                res[i][j] = res[i][j - 1] * a[j] % MOD
        return [res[l][r] for l, r in queries]
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const mod int = 1e9 + 7

func productQueries(n int, queries [][]int) []int {
	a := []int{}
	for n > 0 {
		lb := n & -n
		a = append(a, lb)
		n ^= lb
	}
	na := len(a)
	res := make([][]int, na)
	for i, x := range a {
		res[i] = make([]int, na)
		res[i][i] = x
		for j := i + 1; j < na; j++ {
			res[i][j] = res[i][j-1] * a[j] % mod
		}
	}
	ans := make([]int, len(queries))
	for i, q := range queries {
		ans[i] = res[q[0]][q[1]]
	}
	return ans
}

复杂度分析

  • 时间复杂度：O(m + \log^2 n)，其中 m 为 queries 的长度。
  • 空间复杂度：O(\log^2 n)。返回值不计入。
 Comments
On this page
2438-二的幂数组中查询范围内的乘积
  1. 方法一：暴力
  2. 方法二：预处理