Skip to main content
Talentd

Range Product Queries of Powers - Solution & Explanation

MediumArrayBit ManipulationPrefix Sum17 min readAsked at: Amazon, Goldman Sachs, Google +2
Practice this problem

Problem Statement

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 <= 109
  • 1 <= queries.length <= 105
  • 0 <= starti <= endi < powers.length

Approach Overview

Problem 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 1: Using Bit Manipulation for Powers Array

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Precomputed Product Array for Efficient Query

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].

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Bit Manipulation + Simulation

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)$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(log N) for storing powers derived from binary representation of n.

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.
Space Complexity: O(log N) for powers and prefix product array.

Bit Manipulation + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Manipulation with Direct Range MultiplicationO(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

Video Solution

Range Product Queries of Powers | Simple Explanation | Leetcode 2438 | codestorywithMIK • codestorywithMIK • 9,179 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Product Queries of Powers easy or hard?
Range Product Queries of Powers is considered a Medium difficulty problem. The logic is straightforward once you recognize that n must be decomposed into powers of two, but optimizing repeated range queries with prefix products requires familiarity with range query techniques.
Range Product Queries of Powers Python/Java solution
Python solutions typically extract powers using bit checks and answer queries with prefix products or direct multiplication. Java implementations often use a precomputed product array with modular arithmetic to achieve O(1) query time.
How to solve Range Product Queries of Powers in O(n)?
First extract all powers of two that compose n by scanning its binary bits. Then build a prefix product array where each index stores the cumulative product modulo 1e9+7. Each query product between l and r can be computed in constant time using prefix values and modular inverse.
What is the best approach for Range Product Queries of Powers?
The most efficient approach builds the powers-of-two array from the binary representation of n using bit manipulation, then constructs a prefix product array. This allows each query product to be computed in O(1) time after O(k) preprocessing, where k is the number of set bits in n.
Is Range Product Queries of Powers asked at Google/Amazon/Meta?
Problems involving bit manipulation combined with range queries appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require extracting set bits and using prefix arrays to answer queries efficiently are common interview patterns.
What data structure is used in Range Product Queries of Powers?
The core data structures are a simple array storing the powers of two derived from n and a prefix product array for fast range queries. Bit manipulation is used to generate the array efficiently from the binary representation of n.
What is the time complexity of Range Product Queries of Powers?
Building the powers array takes O(k) time where k is the number of set bits in n. Using a prefix product array, each query is answered in O(1), giving total complexity O(k + q) for q queries. A naive range multiplication approach would take O(k * q).

Ready to solve this problem?

Practice Range Product Queries of Powers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays