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.lengthProblem Overview: You are given an integer n. Break it into powers of two based on the set bits in its binary representation. Build an array containing those powers, then answer queries asking for the product of elements between indices l and r (inclusive) modulo 1e9+7.
Approach 1: Bit Manipulation for Powers Array (O(k * q) time, O(k) space)
Start by extracting all powers of two that form n. Iterate through the bits of n; whenever bit i is set, append 2^i to a list. This uses basic Bit Manipulation to decompose the number into its binary components. Once the powers array is built, handle each query by iterating from index l to r and multiplying the elements while applying modulo 1e9+7. If the array contains k powers and there are q queries, each query may scan up to k elements, resulting in O(k * q) time and O(k) extra space. This approach is straightforward and mirrors the direct interpretation of the problem.
Approach 2: Precomputed Product Array for Efficient Query (O(k + q) time, O(k) space)
The optimization comes from avoiding repeated multiplications across overlapping query ranges. After constructing the powers array from the binary representation of n, build a prefix product array where prefix[i] stores the product of elements from index 0 to i. Each value is computed using modular multiplication. With this structure, a query product from l to r can be calculated in constant time using modular division: prefix[r] * modInverse(prefix[l-1]). This pattern is the multiplicative equivalent of a Prefix Sum array and is commonly used for fast range queries on arrays. Precomputation takes O(k), and each query is answered in O(1), giving total complexity O(k + q) with O(k) space.
Recommended for interviews: Interviewers expect you to first recognize that the array of powers comes directly from the binary representation of n. Building that list with bit operations demonstrates comfort with bit manipulation. The optimized solution adds a prefix product array to answer queries in constant time. Mentioning the naive per-query multiplication shows understanding, but implementing the prefix product approach demonstrates stronger algorithmic thinking for range query problems.
To 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.
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].
Java
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.
We can use bit manipulation (lowbit) to obtain the powers array, and then use simulation to find the answer for each query.
First, for a given positive integer n, we can quickly obtain the value corresponding to the lowest bit 1 in the binary representation through n \& -n, which is the minimum power of 2 factor of the current number. By repeatedly performing this operation on n and subtracting this value, we can sequentially obtain all the powers of 2 corresponding to the set bits, forming the powers array. This array is in increasing order, and its length equals the number of 1s in the binary representation of n.
Next, we need to process each query. For the current query (l, r), we need to calculate
$
answers[i] = \prod_{j=l}^{r} powers[j]
where answers[i] is the answer to the i-th query. Since the query results can be very large, we need to take modulo 10^9 + 7 for each answer.
The time complexity is O(m times log n), where m is the length of the array queries. Ignoring the space consumption of the answer, the space complexity is O(log n)$.
| 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. |
| Bit Manipulation + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation with Direct Range Multiplication | O(k * q) | O(k) | When the number of queries is small and simplicity is preferred |
| Prefix Product Array (Range Product Query) | O(k + q) | O(k) | Best for many queries requiring constant-time range product lookups |
Range Product Queries of Powers | Simple Explanation | Leetcode 2438 | codestorywithMIK • codestorywithMIK • 9,085 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