Watch 10 video solutions for Range Product Queries of Powers, a medium level problem involving Array, Bit Manipulation, Prefix Sum. This walkthrough by codestorywithMIK has 9,085 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |