2438. Range Product Queries of Powers Medium

1/**
2 * [2438] Range Product Queries of Powers
3 *
4 * 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.
5 * 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.
6 * Return an array answers, equal in length to queries, where answers[i] is the answer to the i^th query. Since the answer to the i^th query may be too large, each answers[i] should be returned modulo 10^9 + 7.
7 *  
8 * <strong class="example">Example 1:
9 * 
10 * Input: n = 15, queries = [[0,1],[2,2],[0,3]]
11 * Output: [2,4,64]
12 * Explanation:
13 * For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size.
14 * Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2.
15 * Answer to 2nd query: powers[2] = 4.
16 * Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64.
17 * Each answer modulo 10^9 + 7 yields the same answer, so [2,4,64] is returned.
18 * 
19 * <strong class="example">Example 2:
20 * 
21 * Input: n = 2, queries = [[0,0]]
22 * Output: [2]
23 * Explanation:
24 * For n = 2, powers = [2].
25 * The answer to the only query is powers[0] = 2. The answer modulo 10^9 + 7 is the same, so [2] is returned.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= n <= 10^9
31 * 	1 <= queries.length <= 10^5
32 * 	0 <= starti <= endi < powers.length
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/range-product-queries-of-powers/
38// discuss: https://leetcode.com/problems/range-product-queries-of-powers/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn product_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
44        vec![]
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_2438() {
56    }
57}
58