#2438
Range Product Queries of Powers
specialist · 710 · lc medium +30 · verified · 61.4% accepted · 686 likes · top 61%
Description
A positive integer n can be represented as a sum of distinct powers of 2: n = 2^{a1} + 2^{a2} + ... + 2^{ak} where a1 < a2 < ... < ak. For each query in queries (0-indexed), compute the product of the queries[i]^{th} power (1-indexed from smallest exponent) in this representation modulo 109 + 7.
Given a positive integer n and a 0-indexed integer array queries, return an array of answers for each query.
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.
Code
1
2
3