2438. Range Product Queries of Powers LeetCode Solution
In this guide, you will get 2438. Range Product Queries of Powers LeetCode Solution with the best time and space complexity. The solution to Range Product Queries of Powers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Range Product Queries of Powers
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.
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
Complexity Analysis
Time Complexity: O(q)
Space Complexity: O(q)
2438. Range Product Queries of Powers LeetCode Solution in C++
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
constexpr int kMod = 1'000'000'007;
constexpr int kMaxBit = 30;
vector<int> ans;
vector<int> powers;
for (int i = 0; i < kMaxBit; ++i)
if (n >> i & 1)
powers.push_back(1 << i);
for (const vector<int>& query : queries) {
const int left = query[0];
const int right = query[1];
long prod = 1;
for (int i = left; i <= right; ++i) {
prod *= powers[i];
prod %= kMod;
}
ans.push_back(prod);
}
return ans;
}
}; /* code provided by PROGIEZ */
2438. Range Product Queries of Powers LeetCode Solution in Java
class Solution {
public int[] productQueries(int n, int[][] queries) {
final int kMod = 1_000_000_007;
final int kMaxBit = 30;
int[] ans = new int[queries.length];
List<Integer> powers = new ArrayList<>();
for (int i = 0; i < kMaxBit; ++i)
if ((n >> i & 1) == 1)
powers.add(1 << i);
for (int i = 0; i < queries.length; ++i) {
final int left = queries[i][0];
final int right = queries[i][1];
long prod = 1;
for (int j = left; j <= right; ++j) {
prod *= powers.get(j);
prod %= kMod;
}
ans[i] = (int) prod;
}
return ans;
}
} // code provided by PROGIEZ
2438. Range Product Queries of Powers LeetCode Solution in Python
class Solution:
def productQueries(self, n: int, queries: list[list[int]]) -> list[int]:
kMod = 1_000_000_007
kMaxBit = 30
ans = []
powers = [1 << i for i in range(kMaxBit) if n >> i & 1]
for left, right in queries:
prod = 1
for i in range(left, right + 1):
prod *= powers[i]
prod %= kMod
ans.append(prod)
return ans # code by PROGIEZ
