Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The minimum-length powers-of-two decomposition is given by the set bits of n. Reading bits from low to high lists those powers in sorted order. Exact prefix products let an inclusive range product be recovered by dividing out the earlier prefix.

Approach

Extract each set bit's power of two, then replace the list with cumulative exact products. For query [left, right], take the prefix product at right and, when left > 0, divide by the prefix at left - 1. Apply modulo 10^9 + 7 only after this exact division and append the answer. Reducing prefixes before ordinary division would not preserve the result; these implementations intentionally retain exact products.

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

        while n:
            if n % 2 == 1:
                powers.append(2**pos)
            n //= 2
            pos += 1

        for i in range(1, len(powers)):
            powers[i] *= powers[i - 1]

        res = []

        for l, r in queries:
            curr = powers[r]
            if l > 0:
                curr //= powers[l - 1]
            res.append(curr % MOD)

        return res

Complexity analysis

Let b be n's bit length, q its set-bit count, and m = queries.length. Under the stated n <= 10^9 bound, time is O(b + q + m) and auxiliary storage is O(q), excluding O(m) output. Here b <= 30, and each exact prefix product is a power of two with exponent at most 0 + ... + 29 = 435: Python integers need at most 436 bits, while JavaScript Number represents these powers and their power-of-two quotients exactly without overflow. Prefix division precedes the final modulus. For unbounded n, Python multiplication/division costs are not constant and prefix storage is up to O(q*b^2) bits; the linear operation count is not a general bit-time bound.