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 <= 1091 <= queries.length <= 1050 <= starti <= endi < powers.lengthTo construct the powers array, observe that the number n can be represented as a sum of distinct powers of two, evident from its binary form. For example, if n = 15, its binary representation is 1111, signifying that powers = [1, 2, 4, 8]. We take note of each position with a 1 in the binary representation and include 2^i in the array.
After forming the powers array, compute the product of elements between the specified indices for each query. The product calculation involves iterating through the specified range and applying modulo 10^9 + 7 at every multiplication step to prevent overflow.
The function range_product_queries computes the result by first determining the powers list through the binary decomposition of n. It iterates through each query, calculating the product of the elements within the specified range, applying the modulo at each multiplication step. Finally, it returns the results for all queries.
C++
Time Complexity: O(Q * L) where Q is the number of queries and L is the average length of the ranges in queries.
Space Complexity: O(log N) for storing powers derived from binary representation of n.
After determining the powers array, we can further optimize the query process using a prefix product array. This array allows us to compute the product of a range in constant time by storing cumulative products modulo 10^9 + 7. The prefix product array prefix_prod is constructed such that prefix_prod[i] contains the product of all elements from the start up to i.
For each query, the product from index left to right can be obtained using prefix_prod[right + 1] / prefix_prod[left], followed by applying modulo arithmetic to manage large numbers.
Here, the Java solution constructs a powers list similarly. It then creates a prefixProd array for quick range product computation. The function modInverse is used to handle division under modulo by Fermat's Little Theorem, allowing the computation of prefixProd[right + 1] / prefixProd[left].
JavaScript
Time Complexity: O(log N + Q) where Q is the number of queries. Each query takes constant time due to precomputed prefix products.
Space Complexity: O(log N) for powers and prefix product array.
| Approach | Complexity |
|---|---|
| Using Bit Manipulation for Powers Array | Time Complexity: O(Q * L) where Q is the number of queries and L is the average length of the ranges in queries. |
| Precomputed Product Array for Efficient Query | Time Complexity: O(log N + Q) where Q is the number of queries. Each query takes constant time due to precomputed prefix products. |
I HATE This Coding Question, but FAANG Loves it! | Majority Element - Leetcode 169 • Greg Hogg • 2,093,930 views views
Watch 9 more video solutions →Practice Range Product Queries of Powers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor