Range product queries of powers

Array Bit Manipulation Prefix Sum

61.4% acceptance

Feb 25, 2026

686

152

Given a positive integer n, there exists a 0-indexed array called powers, com posed 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 array answers, equal in length to queries, where answers[i] is the answer to the ith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 109 + 7. *

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn product_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
    const MOD: i64 = 1_000_000_007;
    let mut powers: Vec<i64> = Vec::new();
    for i in 0..30 {
      if (n >> i) & 1 == 1 {
        powers.push(1i64 << i);
      }
    }
    let len = powers.len();
    let mut prefix = vec![1i64; len + 1];
    for i in 0..len {
      prefix[i + 1] = prefix[i] * powers[i] % MOD;
    }
    // product from l to r = prefix[r+1] / prefix[l], but we need modular inverse
    // Instead, just compute directly since powers has at most 30 elements
    queries.iter().map(|q| {
      let (l, r) = (q[0] as usize, q[1] as usize);
      let mut prod = 1i64;
      for i in l..=r {
        prod = prod * powers[i] % MOD;
      }
      prod as i32
    }).collect()
  }
}