LeetCode 2438 - Range Product Queries of Powers

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

The problem defines a special array called powers. This array is built from the binary representation of n.

Every positive integer can be uniquely represented as a sum of powers of two. For example:

15 = 1 + 2 + 4 + 8
13 = 1 + 4 + 8
10 = 2 + 8

The array powers contains exactly those powers of two that appear in the binary decomposition of n, sorted in non-decreasing order.

For example:

If n = 15, then powers = [1, 2, 4, 8]
If n = 13, then powers = [1, 4, 8]

The phrase “minimum number of powers of 2” is important. We are not allowed to split powers unnecessarily. For example, 8 should remain 8, not 4 + 4. Because binary representation is unique, there is exactly one valid powers array.

Each query [left, right] asks for the product:

$$powers[left] \times powers[left+1] \times \cdots \times powers[right]$$

The answer can become very large, so every result must be returned modulo:

$$10^9 + 7$$

The constraints provide important insight:

n <= 10^9
queries.length <= 10^5

Although there may be many queries, the size of powers is actually very small. Since n <= 10^9, its binary representation has at most 30 bits. That means powers.length <= 30.

This dramatically changes the problem. Even simple per-query operations become affordable because the array is tiny.

Some important edge cases include:

n being a single power of two, such as n = 8
Queries covering only one element
Queries covering the entire array
Very large numbers of queries
Powers containing gaps, such as n = 10 producing [2, 8]

The problem guarantees that all query indices are valid.

Approaches

Brute Force Approach

The most direct solution is:

Construct the powers array.
For every query, multiply all elements from left to right.
Apply modulo after multiplication.

For example, if:

powers = [1, 2, 4, 8]
query = [1, 3]

We compute:

2 × 4 × 8 = 64

This works correctly because it directly follows the definition of the query.

However, if we process every query by iterating through the requested range, the total complexity becomes:

$$O(q \times m)$$

Where:

q is the number of queries
m is the length of powers

Even though m is small here, we can still improve the solution using prefix products or mathematical observations.

Key Insight

Every element in powers is itself a power of two.

Suppose:

powers = [2^a, 2^b, 2^c]

Then:

$$2^a \times 2^b \times 2^c = 2^{a+b+c}$$

Instead of multiplying large numbers repeatedly, we can work with exponents.

For example:

powers = [1, 2, 4, 8]
         [2^0, 2^1, 2^2, 2^3]

A query [1, 3] corresponds to:

$$2^1 \times 2^2 \times 2^3 = 2^{1+2+3} = 2^6 = 64$$

So the problem becomes:

Extract the exponents of all set bits in n
Build prefix sums of exponents
For each query:

compute exponent sum in O(1)
calculate $2^{sum} \mod (10^9+7)$

This is cleaner and more efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q × m)	O(m)	Multiplies every element for every query
Optimal	O(m + q)	O(m)	Uses exponent prefix sums and fast modular exponentiation

Here:

m = powers.length
q = queries.length

Since m <= 30, both are acceptable, but the optimal approach is more elegant and scalable.

Algorithm Walkthrough

Initialize an empty list called exponents.

This list will store the positions of set bits in n.

For example:

n = 13 = 1101₂

Set bits appear at positions:

0, 2, 3

So:

exponents = [0, 2, 3]

Extract all set bits from n.

Iterate through bit positions from low to high.

If bit i is set, append i to exponents.

This works because:

2^i

corresponds exactly to the power contributed by that bit. 3. Build a prefix sum array over the exponents.

Suppose:

exponents = [0, 1, 2, 3]

Then:

prefix = [0, 0, 1, 3, 6]

The extra leading zero simplifies range calculations. 4. Process each query.

For query [left, right], compute:

exponent_sum = prefix[right + 1] - prefix[left]

This gives the total exponent contributed by the range. 5. Compute the final product.

Since:

$$2^a \times 2^b = 2^{a+b}$$

the answer is:

$$2^{exponent_sum} \mod (10^9+7)$$

Use fast modular exponentiation with Python’s built-in pow. 6. Append the result to the answer list. 7. Return the final list of answers.

Why it works

Each element in powers is uniquely represented as $2^k$. Multiplying powers of two adds their exponents:

$$2^a \times 2^b = 2^{a+b}$$

Therefore, every query product can be reduced to summing exponents over a range. Prefix sums allow those range sums to be computed in constant time, and modular exponentiation efficiently computes the final value.

Because binary decomposition is unique, the constructed powers array is always correct.

Python Solution

from typing import List

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7

        exponents = []

        bit_position = 0
        while n > 0:
            if n & 1:
                exponents.append(bit_position)
            n >>= 1
            bit_position += 1

        prefix = [0]

        for exponent in exponents:
            prefix.append(prefix[-1] + exponent)

        answers = []

        for left, right in queries:
            exponent_sum = prefix[right + 1] - prefix[left]
            answers.append(pow(2, exponent_sum, MOD))

        return answers

The implementation begins by extracting the set bits from n. Each set bit corresponds to a power of two, and its bit position becomes the exponent stored in the exponents array.

The loop:

while n > 0:

processes the binary representation from least significant bit to most significant bit. Whenever:

n & 1

is true, the current bit is set.

Next, the code constructs a prefix sum array. The extra initial zero makes range sum calculations straightforward.

For each query, the code computes the total exponent contributed by the requested subarray. Instead of multiplying powers individually, it directly computes:

2^(sum of exponents)

using Python’s efficient modular exponentiation:

pow(base, exponent, mod)

This keeps the implementation concise and efficient.

Go Solution

package main

func productQueries(n int, queries [][]int) []int {
	const MOD int = 1_000_000_007

	exponents := []int{}

	bitPosition := 0

	for n > 0 {
		if n&1 == 1 {
			exponents = append(exponents, bitPosition)
		}

		n >>= 1
		bitPosition++
	}

	prefix := make([]int, len(exponents)+1)

	for i, exponent := range exponents {
		prefix[i+1] = prefix[i] + exponent
	}

	answers := make([]int, 0, len(queries))

	for _, query := range queries {
		left := query[0]
		right := query[1]

		exponentSum := prefix[right+1] - prefix[left]

		answers = append(answers, modPow(2, exponentSum, MOD))
	}

	return answers
}

func modPow(base, exponent, mod int) int {
	result := 1

	base %= mod

	for exponent > 0 {
		if exponent&1 == 1 {
			result = (result * base) % mod
		}

		base = (base * base) % mod
		exponent >>= 1
	}

	return result
}

The Go implementation follows the same algorithm as the Python version. Since Go does not provide a built-in modular exponentiation function equivalent to Python’s pow(base, exp, mod), we implement binary exponentiation manually in modPow.

Slices are used for both the exponent list and prefix sums. Since the maximum number of bits is very small, memory usage remains tiny.

All arithmetic safely fits inside Go’s int type because intermediate values are reduced modulo 1e9+7.

Worked Examples

Example 1

Input:

n = 15
queries = [[0,1],[2,2],[0,3]]

Step 1: Build powers

Binary representation:

15 = 1111₂

Set bits:

Bit Position	Power
0	1
1	2
2	4
3	8

So:

powers = [1, 2, 4, 8]
exponents = [0, 1, 2, 3]

Step 2: Prefix sums

Index	Prefix Value
0	0
1	0
2	1
3	3
4	6

Step 3: Process queries

Query `[0,1]`

Exponent sum:

prefix[2] - prefix[0]
= 1 - 0
= 1

Answer:

$$2^1 = 2$$

Query `[2,2]`

Exponent sum:

prefix[3] - prefix[2]
= 3 - 1
= 2

Answer:

$$2^2 = 4$$

Query `[0,3]`

Exponent sum:

prefix[4] - prefix[0]
= 6 - 0
= 6

Answer:

$$2^6 = 64$$

Final output:

[2, 4, 64]

Example 2

Input:

n = 2
queries = [[0,0]]

Binary representation:

10₂

Set bit:

Bit Position	Power
1	2

So:

powers = [2]
exponents = [1]

Prefix sums:

prefix = [0, 1]

Query [0,0]:

prefix[1] - prefix[0]
= 1

Answer:

$$2^1 = 2$$

Final output:

[2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + q)	Extract bits and build prefix sums in O(m), answer each query in O(1)
Space	O(m)	Stores exponents and prefix sums

Here:

m is the number of set bits in n
q is the number of queries

Since n <= 10^9, we have at most 30 bits, so m <= 30. The algorithm is therefore extremely efficient in practice.

Test Cases

from typing import List

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7

        exponents = []

        bit_position = 0

        while n > 0:
            if n & 1:
                exponents.append(bit_position)

            n >>= 1
            bit_position += 1

        prefix = [0]

        for exponent in exponents:
            prefix.append(prefix[-1] + exponent)

        answers = []

        for left, right in queries:
            exponent_sum = prefix[right + 1] - prefix[left]
            answers.append(pow(2, exponent_sum, MOD))

        return answers

solution = Solution()

assert solution.productQueries(15, [[0, 1], [2, 2], [0, 3]]) == [2, 4, 64]  # Provided example
assert solution.productQueries(2, [[0, 0]]) == [2]  # Single power of two
assert solution.productQueries(13, [[0, 0], [1, 2]]) == [1, 32]  # Non-consecutive powers
assert solution.productQueries(1, [[0, 0]]) == [1]  # Smallest possible n
assert solution.productQueries(31, [[0, 4]]) == [32768]  # Entire range
assert solution.productQueries(10, [[0, 1], [1, 1]]) == [16, 8]  # Mixed queries
assert solution.productQueries(1024, [[0, 0]]) == [1024]  # Large single power
assert solution.productQueries(7, [[0, 2], [1, 2], [0, 1]]) == [8, 8, 2]  # Multiple overlapping queries

Test	Why
`n=15` standard example	Validates normal multi-query behavior
`n=2`	Tests single-element powers array
`n=13`	Tests gaps in binary representation
`n=1`	Smallest valid input
`n=31` full range query	Tests complete multiplication
`n=10` mixed ranges	Tests subarray handling
`n=1024`	Tests large power of two
Overlapping queries	Ensures prefix sums work correctly

Edge Cases

One important edge case occurs when n itself is already a power of two. For example:

n = 8

The powers array becomes:

[8]

A buggy implementation might incorrectly split this into smaller powers like [4, 4] or [2, 2, 2, 2]. Our implementation avoids this because it directly extracts set bits from the binary representation, which naturally preserves the minimal decomposition.

Another important case is when a query covers exactly one element. For example:

queries = [[2, 2]]

In this situation, the product should simply equal that single power. Prefix sums handle this cleanly because:

prefix[right + 1] - prefix[left]

still produces the correct exponent for a single position.

A third edge case involves sparse binary representations, such as:

n = 10

Binary:

1010₂

The powers array becomes:

[2, 8]

There are gaps between exponents. A naive implementation that assumes consecutive powers would fail here. Our algorithm correctly records only the set bit positions, so sparse representations work naturally.

Finally, the problem allows up to 10^5 queries. Recomputing products from scratch for every query could become inefficient in larger variants of the problem. Using prefix sums ensures each query is answered in constant time.

LeetCode 2438 - Range Product Queries of Powers

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Build powers

Step 2: Prefix sums

Step 3: Process queries

Query [0,1]

Query [2,2]

Query [0,3]

Example 2

Complexity Analysis

Test Cases

Edge Cases

Query `[0,1]`

Query `[2,2]`

Query `[0,3]`