Range Product Queries of Powers
MediumUpdated: Aug 2, 2025
Practice on:
Problem
Given a positive integer n, there exists a 0-indexed array called
powers, composed of the minimum number of powers of 2 that sum to n.
The array is sorted in non-decreasing order, and there is only one way to form the array.
You are also given a 0-indexed 2D integer array queries, where
queries[i] = [lefti, righti]. Each queries[i] represents a query where you have to find the product of all powers[j] with lefti <= j <= righti.
Return an arrayanswers , equal in length toqueries , whereanswers[i]is the answer to theith query. Since the answer to the
ith query may be too large, each answers[i] should be returned modulo
10^9 + 7.
Examples
Example 1
Input: n = 15, queries = [[0,1],[2,2],[0,3]]
Output: [2,4,64]
Explanation:
For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size.
Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2.
Answer to 2nd query: powers[2] = 4.
Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64.
Each answer modulo 10^9 + 7 yields the same answer, so [2,4,64] is returned.
Example 2
Input: n = 2, queries = [[0,0]]
Output: [2]
Explanation:
For n = 2, powers = [2].
The answer to the only query is powers[0] = 2. The answer modulo 10^9 + 7 is the same, so [2] is returned.
Constraints
1 <= n <= 10^91 <= queries.length <= 10^50 <= starti <= endi < powers.length
Solution
Method 1 – Bit Manipulation and Prefix Product
Intuition
The array powers is the list of powers of 2 that sum to n, i.e., the set bits in n as powers of 2. For each query, the product of a subarray is just the product of the corresponding powers, which is another power of 2. We can precompute prefix products for fast queries.
Approach
- Extract all set bits of
nand store their corresponding powers of 2 in a listpowers(from least to most significant bit). - Compute prefix products modulo
10^9+7. - For each query
[l, r], compute the product asprefix[r+1] // prefix[l](or using modular inverse for modulo division).
Code
C++
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
vector<int> p;
for (int i = 0; i < 32; ++i) if (n & (1 << i)) p.push_back(1 << i);
int m = p.size(), mod = 1e9+7;
vector<long long> pre(m+1, 1);
for (int i = 0; i < m; ++i) pre[i+1] = pre[i] * p[i] % mod;
vector<int> ans;
auto modinv = [&](long long a) {
long long res = 1, b = mod-2;
while (b) { if (b&1) res = res*a%mod; a = a*a%mod; b>>=1; }
return res;
};
for (auto& q : queries) {
int l = q[0], r = q[1];
ans.push_back(pre[r+1] * modinv(pre[l]) % mod);
}
return ans;
}
};
Go
func productQueries(n int, queries [][]int) []int {
mod := int(1e9+7)
p := []int{}
for i := 0; i < 32; i++ {
if n&(1<<i) > 0 {
p = append(p, 1<<i)
}
}
m := len(p)
pre := make([]int, m+1)
pre[0] = 1
for i := 0; i < m; i++ {
pre[i+1] = pre[i] * p[i] % mod
}
modinv := func(a int) int {
res, b := 1, mod-2
aa := a
for b > 0 {
if b&1 == 1 {
res = res * aa % mod
}
aa = aa * aa % mod
b >>= 1
}
return res
}
ans := make([]int, len(queries))
for i, q := range queries {
l, r := q[0], q[1]
ans[i] = pre[r+1] * modinv(pre[l]) % mod
}
return ans
}
Java
class Solution {
public int[] productQueries(int n, int[][] queries) {
List<Integer> p = new ArrayList<>();
for (int i = 0; i < 32; ++i) if ((n & (1 << i)) > 0) p.add(1 << i);
int m = p.size(), mod = (int)1e9+7;
long[] pre = new long[m+1];
pre[0] = 1;
for (int i = 0; i < m; ++i) pre[i+1] = pre[i] * p.get(i) % mod;
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
int l = queries[i][0], r = queries[i][1];
ans[i] = (int)(pre[r+1] * powmod(pre[l], mod-2, mod) % mod);
}
return ans;
}
private long powmod(long a, int b, int mod) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
}
Kotlin
class Solution {
fun productQueries(n: Int, queries: Array<IntArray>): IntArray {
val p = mutableListOf<Int>()
for (i in 0 until 32) if ((n and (1 shl i)) > 0) p.add(1 shl i)
val m = p.size; val mod = 1_000_000_007
val pre = LongArray(m+1) { 1L }
for (i in 0 until m) pre[i+1] = pre[i] * p[i] % mod
fun modinv(a: Long): Long {
var res = 1L; var b = mod-2; var aa = a
while (b > 0) {
if (b and 1 == 1) res = res * aa % mod
aa = aa * aa % mod; b = b shr 1
}
return res
}
return queries.map { (l, r) -> (pre[r+1] * modinv(pre[l]) % mod).toInt() }.toIntArray()
}
}
Python
from typing import List
class Solution:
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
mod = 10**9 + 7
p = [1 << i for i in range(32) if (n >> i) & 1]
pre = [1]
for x in p:
pre.append(pre[-1] * x % mod)
def modinv(a: int) -> int:
return pow(a, mod-2, mod)
return [(pre[r+1] * modinv(pre[l])) % mod for l, r in queries]
Rust
impl Solution {
pub fn product_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let modn = 1_000_000_007i64;
let mut p = vec![];
for i in 0..32 {
if (n >> i) & 1 == 1 { p.push(1 << i); }
}
let mut pre = vec![1i64];
for &x in &p { pre.push(pre.last().unwrap() * (x as i64) % modn); }
let modinv = |a: i64| -> i64 {
let mut res = 1i64; let mut b = modn-2; let mut aa = a;
while b > 0 {
if b & 1 == 1 { res = res * aa % modn; }
aa = aa * aa % modn; b >>= 1;
}
res
};
queries.iter().map(|q| (pre[q[1] as usize + 1] * modinv(pre[q[0] as usize]) % modn) as i32).collect()
}
}
TypeScript
class Solution {
productQueries(n: number, queries: number[][]): number[] {
const mod = 1e9+7;
const p: number[] = [];
for (let i = 0; i < 32; ++i) if ((n >> i) & 1) p.push(1 << i);
const m = p.length;
const pre: number[] = [1];
for (let i = 0; i < m; ++i) pre.push(pre[pre.length-1] * p[i] % mod);
const modinv = (a: number): number => {
let res = 1, b = mod-2, aa = a;
while (b > 0) {
if (b & 1) res = res * aa % mod;
aa = aa * aa % mod; b >>= 1;
}
return res;
};
return queries.map(([l, r]) => pre[r+1] * modinv(pre[l]) % mod);
}
}
Complexity
- ⏰ Time complexity:
O(Q + log n), where Q is the number of queries. Extracting powers is O(log n), prefix computation is O(log n), and each query is O(1). - 🧺 Space complexity:
O(log n), for storing the powers and prefix products.