2438. Range Product Queries of Powers
Medium
257
41

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 * powers = 1 * 2 = 2.
Answer to 2nd query: powers = 4.
Answer to 3rd query: powers * powers * powers * powers = 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: 
Explanation:
For n = 2, powers = .
The answer to the only query is powers = 2. The answer modulo 109 + 7 is the same, so  is returned.
```

Constraints:

• `1 <= n <= 109`
• `1 <= queries.length <= 105`
• `0 <= starti <= endi < powers.length`
Accepted
13.6K
Submissions
34.9K
Acceptance Rate
39.0%

Seen this question in a real interview before?
1/4
Yes
No

Discussion (0)

Related Topics