1181MediumArrayBit ManipulationPrefix Sum

Products Over Stretches of the Binary Pieces

Tracked in this browser only

Trains the technique from

LeetCode 2438Range Product Queries of Powers

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

The number n can be written as a sum of powers of two, each used at most once, and in exactly one way. List those powers in increasing order and call the list pieces.

Each entry of queries is a pair [from, to] naming a stretch of pieces, both ends included. Answer each with the product of the pieces in that stretch, taken modulo 10^9 + 7.

Return the answers in the order the queries are asked.

Examples

Example 1

Input: n = 7, queries = [[0, 2]]
Output: [8]

Seven splits into 1, 2 and 4, and the whole stretch multiplies to 8.

Example 2

Input: n = 12, queries = [[0, 0], [1, 1]]
Output: [4, 8]

Twelve splits into 4 and 8, and each query asks for one of them on its own.

Example 3

Input: n = 255, queries = [[0, 7]]
Output: [268435456]

The eight pieces are the powers of two from 1 up to 128, so their exponents add to 28 and the product is two to that.

Constraints

1 <= n <= 10^9
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1]

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def product_queries(n: int, queries: list[list[int]]) -> list[int]:

Java

public int[] productQueries(int n, int[][] queries)

The intended approach

Time O(log n + q log n) for q queries.Space O(log n) for the running totals.

The pieces are read straight off the bits of `n`: a bit set at place `p` contributes two to the `p`. Since every piece is a power of two, the product over a stretch is also a power of two, and its exponent is simply the exponents of that stretch added up. So keep the running totals of the exponents. Then each query is one subtraction to get the exponent and one modular power to turn it into an answer, rather than a walk over the stretch multiplying as it goes. Reducing at the end with a modular power also keeps the working small, since the exponent of a full stretch can reach into the hundreds and the plain product would be a several-hundred-bit number.

Pythonentry point: product_queries

def product_queries(n, queries):
    mod = 1000000007
    places = []
    place = 0
    rest = n
    while rest:
        if rest & 1:
            places.append(place)
        rest >>= 1
        place += 1
    running = [0] * (len(places) + 1)
    for i in range(len(places)):
        running[i + 1] = running[i] + places[i]
    out = []
    for pair in queries:
        power = running[pair[1] + 1] - running[pair[0]]
        out.append(pow(2, power, mod))
    return out

The obvious version

Read the pieces off the bits, then answer each query by multiplying the pieces of the stretch together as whole numbers, however large that grows, and reducing only at the very end. Costs the stretch length per query and arithmetic on several-hundred-bit numbers.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_product_queries(n, queries):
    mod = 1000000007
    pieces = []
    place = 0
    rest = n
    while rest:
        if rest & 1:
            pieces.append(1 << place)
        rest >>= 1
        place += 1
    out = []
    for pair in queries:
        total = 1
        for i in range(pair[0], pair[1] + 1):
            total *= pieces[i]
        out.append(total % mod)
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in