# Range Product Queries of Powers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/range-product-queries-of-powers)
Canonical: https://scaleengineer.com/dsa/problems/range-product-queries-of-powers
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm)
---
## 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 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`.

**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 109 + 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 109 + 7 is the same, so [2] is returned.

**Constraints:**

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

# Approaches
## Brute-force Simulation per Query
This straightforward approach first determines the `powers` array by decomposing the input number `n` into its constituent powers of two. This is equivalent to finding the set bits in the binary representation of `n`. After constructing the `powers` array, it processes each query by iterating from the `left` index to the `right` index and calculating the product of the elements, taking the modulo at each step to prevent overflow.
**Time:** O(L + Q * L), where `Q` is the number of queries and `L` is the length of the `powers` array. `L` is the number of set bits in `n`, so `L <= ceil(log2(n))`. The `O(L)` part is for building the `powers` array. The `O(Q * L)` part is for processing all queries, as each query can take up to `O(L)` time. · **Space:** O(L + Q), where `L` is the length of the `powers` array (`L <= log n`) and `Q` is the number of queries. This space is used for storing the `powers` array and the `answers` array.
**Pros:** Easy to understand and implement.; Sufficiently fast for the given constraints, although not the most optimal.
**Cons:** Performs redundant calculations. If two queries have overlapping ranges, the product for the common part is re-calculated.; Time complexity is dependent on the length of the query ranges, making it slower for queries with large ranges.
### Explanation
The first step is to generate the `powers` array. A number `n` can be uniquely represented as a sum of distinct powers of 2. These powers of 2 correspond to the positions of '1's in the binary representation of `n`. For example, if `n=15` (binary `1111`), the powers are `2^0, 2^1, 2^2, 2^3`, so `powers = [1, 2, 4, 8]`. We can generate this array by iterating through the bits of `n`.

Once the `powers` array is ready, we can answer each query. For a query `[left, right]`, we simply multiply the elements `powers[left], powers[left+1], ..., powers[right]`. To handle large products, all multiplications are performed under the modulo `10^9 + 7`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        long MOD = 1_000_000_007;
        List<Long> powers = new ArrayList<>();
        for (int i = 0; i < 31; i++) {
            if (((n >> i) & 1) == 1) {
                powers.add(1L << i);
            }
        }

        int[] answers = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            long product = 1;
            for (int j = left; j <= right; j++) {
                product = (product * powers.get(j)) % MOD;
            }
            answers[i] = (int) product;
        }
        return answers;
    }
}
```
### Algorithm
- Initialize an empty list, `powers`.
- Iterate from bit position `i = 0` to 30.
- If the `i`-th bit of `n` is set (i.e., `(n >> i) & 1 == 1`), add `2^i` to the `powers` list.
- Initialize an `answers` array with the same length as the `queries` array.
- For each query `[left, right]` at index `i` in `queries`:
  - Initialize a variable `currentProduct` to 1.
  - Iterate from `j = left` to `right`.
  - In each step, update `currentProduct = (currentProduct * powers.get(j)) % 1000000007`.
  - Store the final `currentProduct` in `answers[i]`.
- Return the `answers` array.

## Prefix Sum of Exponents with Modular Exponentiation
A more efficient approach leverages a mathematical property of exponents: the product of powers of the same base is the base raised to the sum of the exponents. Instead of calculating the product of `powers[j]` directly, we can calculate the sum of their exponents and then compute `2` raised to this total exponent. To quickly find the sum of exponents for any given range, we can precompute a prefix sum array.
**Time:** O(L + Q * log(S)), where `L` is the number of set bits in `n` (`L <= log n`), `Q` is the number of queries, and `S` is the maximum possible sum of exponents. The `O(L)` part is for building the `exponents` and `prefixExponents` arrays. The sum of exponents `S` is at most `O(L^2)`. The modular exponentiation takes `O(log S)` time. Since `L` is small (at most 30), `log S` is a small constant, making the query time effectively `O(1)`. The total complexity is approximately `O(L + Q)`. · **Space:** O(L + Q), where `L` is the number of set bits in `n` (`L <= log n`) and `Q` is the number of queries. This space is for the `exponents`, `prefixExponents`, and `answers` arrays.
**Pros:** Very efficient, as each query is processed in near-constant time after an initial setup.; Scales well with a large number of queries.
**Cons:** Requires additional space for the `exponents` and `prefixExponents` arrays.; Implementation is more complex, involving prefix sums and modular exponentiation.
### Explanation
The key insight is that `powers[left] * ... * powers[right]` is equal to `(2^e_left * ... * 2^e_right) = 2^(e_left + ... + e_right)`, where `e_j` is the exponent of the `j`-th power of two in the `powers` array.

This transforms the problem from a range product query to a range sum query. Range sum queries can be answered efficiently in `O(1)` time using a prefix sum array.

First, we generate a list of exponents corresponding to the set bits of `n`. For `n=15` (binary `1111`), the exponents are `0, 1, 2, 3`.

Then, we build a prefix sum array on these exponents. For `exponents = [0, 1, 2, 3]`, the prefix sum array would be `[0, 0, 1, 3, 6]` (with an extra leading zero for easier calculation).

For a query `[left, right]`, the sum of exponents is `prefixExponents[right+1] - prefixExponents[left]`. Let this sum be `S`.

The final step is to compute `(2^S) % MOD`. This is done using the binary exponentiation (or exponentiation by squaring) algorithm, which is efficient for large exponents.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private long power(long base, long exp) {
        long res = 1;
        long MOD = 1_000_000_007;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    public int[] productQueries(int n, int[][] queries) {
        List<Integer> exponents = new ArrayList<>();
        for (int i = 0; i < 31; i++) {
            if (((n >> i) & 1) == 1) {
                exponents.add(i);
            }
        }

        int k = exponents.size();
        long[] prefixExponents = new long[k + 1];
        for (int i = 0; i < k; i++) {
            prefixExponents[i + 1] = prefixExponents[i] + exponents.get(i);
        }

        int[] answers = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            long totalExponent = prefixExponents[right + 1] - prefixExponents[left];
            answers[i] = (int) power(2, totalExponent);
        }
        return answers;
    }
}
```
### Algorithm
- Initialize an empty list, `exponents`.
- Iterate from bit position `i = 0` to 30. If the `i`-th bit of `n` is set, add `i` to the `exponents` list.
- Let `k` be the size of `exponents`. Create a `prefixExponents` array of size `k + 1`.
- Compute the prefix sums: `prefixExponents[0] = 0`, and for `i` from 0 to `k-1`, `prefixExponents[i+1] = prefixExponents[i] + exponents.get(i)`.
- Initialize an `answers` array.
- For each query `[left, right]` at index `i`:
  - Calculate the total exponent for the range: `totalExponent = prefixExponents[right + 1] - prefixExponents[left]`.
  - Compute `result = power(2, totalExponent, 1000000007)` using modular exponentiation.
  - Store `result` in `answers[i]`.
- Return `answers`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int[] productQueries(int n, int[][] queries) {
    int[] powers = new int[Integer.bitCount(n)];
    for (int i = 0; n > 0; ++i) {
      int x = n & -n;
      powers[i] = x;
      n -= x;
    }
    int[] ans = new int[queries.length];
    for (int i = 0; i < ans.length; ++i) {
      long x = 1;
      int l = queries[i][0], r = queries[i][1];
      for (int j = l; j <= r; ++j) {
        x = (x * powers[j]) % MOD;
      }
      ans[i] = (int)x;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  vector<int> productQueries(int n, vector<vector<int>> &queries) {
    vector<int> powers;
    while (n) {
      int x = n & -n;
      powers.emplace_back(x);
      n -= x;
    }
    vector<int> ans;
    for (auto &q : queries) {
      int l = q[0], r = q[1];
      long long x = 1l;
      for (int j = l; j <= r; ++j) {
        x = (x * powers[j]) % mod;
      }
      ans.emplace_back(x);
    }
    return ans;
  }
};

```

### Python

```python
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 y in powers[l: r + 1]: x = (x * y) % mod ans . append(x) return ans

```