Range Product Queries of Powers
MedPrompt
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.length
Approaches
2 approaches with complexity analysis and trade-offs.
This straightforward approach first determines the powers array by decomposing the input number n into its constituent powers of two. This is equivalent to finding the set bits in the binary representation of n. After constructing the powers array, it processes each query by iterating from the left index to the right index and calculating the product of the elements, taking the modulo at each step to prevent overflow.
Algorithm
- Initialize an empty list,
powers. - Iterate from bit position
i = 0to 30. - If the
i-th bit ofnis set (i.e.,(n >> i) & 1 == 1), add2^ito thepowerslist. - Initialize an
answersarray with the same length as thequeriesarray. - For each query
[left, right]at indexiinqueries:- Initialize a variable
currentProductto 1. - Iterate from
j = lefttoright. - In each step, update
currentProduct = (currentProduct * powers.get(j)) % 1000000007. - Store the final
currentProductinanswers[i].
- Initialize a variable
- Return the
answersarray.
Walkthrough
The first step is to generate the powers array. A number n can be uniquely represented as a sum of distinct powers of 2. These powers of 2 correspond to the positions of '1's in the binary representation of n. For example, if n=15 (binary 1111), the powers are 2^0, 2^1, 2^2, 2^3, so powers = [1, 2, 4, 8]. We can generate this array by iterating through the bits of n.
Once the powers array is ready, we can answer each query. For a query [left, right], we simply multiply the elements powers[left], powers[left+1], ..., powers[right]. To handle large products, all multiplications are performed under the modulo 10^9 + 7.
import java.util.ArrayList;import java.util.List; class Solution { public int[] productQueries(int n, int[][] queries) { long MOD = 1_000_000_007; List<Long> powers = new ArrayList<>(); for (int i = 0; i < 31; i++) { if (((n >> i) & 1) == 1) { powers.add(1L << i); } } int[] answers = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int left = queries[i][0]; int right = queries[i][1]; long product = 1; for (int j = left; j <= right; j++) { product = (product * powers.get(j)) % MOD; } answers[i] = (int) product; } return answers; }}Complexity
Time
O(L + Q * L), where `Q` is the number of queries and `L` is the length of the `powers` array. `L` is the number of set bits in `n`, so `L <= ceil(log2(n))`. The `O(L)` part is for building the `powers` array. The `O(Q * L)` part is for processing all queries, as each query can take up to `O(L)` time.
Space
O(L + Q), where `L` is the length of the `powers` array (`L <= log n`) and `Q` is the number of queries. This space is used for storing the `powers` array and the `answers` array.
Trade-offs
Pros
Easy to understand and implement.
Sufficiently fast for the given constraints, although not the most optimal.
Cons
Performs redundant calculations. If two queries have overlapping ranges, the product for the common part is re-calculated.
Time complexity is dependent on the length of the query ranges, making it slower for queries with large ranges.
Solutions
Solution
class Solution {private static final int MOD = (int)1 e9 + 7;public int[] productQueries(int n, int[][] queries) { int[] powers = new int[Integer.bitCount(n)]; for (int i = 0; n > 0; ++i) { int x = n & -n; powers[i] = x; n -= x; } int[] ans = new int[queries.length]; for (int i = 0; i < ans.length; ++i) { long x = 1; int l = queries[i][0], r = queries[i][1]; for (int j = l; j <= r; ++j) { x = (x * powers[j]) % MOD; } ans[i] = (int)x; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.