We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Range Product Queries of Powers

Number: 2529

Difficulty: Medium

Paid? No

Companies: Goldman Sachs

Problem Description

Given a positive integer n, construct the 0-indexed array powers by decomposing n into the minimum number of powers of 2 whose sum equals n. The array is sorted in non-decreasing order. Then, given a list of queries where each query specifies indices [left, right], compute the product of the subarray powers[left] to powers[right] modulo 10^9+7.

Key Insights

  • The array powers is unique and corresponds to the 1-bits in the binary representation of n.
  • Since the binary representation lists bits from least significant (smallest power) to most significant (largest power), the list is naturally non-decreasing.
  • Use a prefix product array to answer range product queries efficiently.
  • To compute range product from L to R, use: product = prefix[R+1] * modInverse(prefix[L]) modulo (10^9+7).
  • Modular inverse can be computed using Fermat’s Little Theorem, as 10^9+7 is prime.

Space and Time Complexity

Time Complexity: O(B + Q), where B is the number of bits in n (at most ~31) and Q is the number of queries. Space Complexity: O(B), for the powers array and prefix product array.

Solution

The solution begins by determining the binary representation of n. For each set bit, compute 2^(bit position) and append to the powers array. The array is naturally non-decreasing since lower bits correspond to smaller powers of 2. Next, construct a prefix product array where each element stores the product of the powers up to the current index modulo 10^9+7. For each query [L, R], compute the subarray product as (prefix[R+1] * modInverse(prefix[L])) mod (10^9+7). The modular inverse is calculated using Fermat's little theorem since the modulus is prime.

Code Solutions

MOD = 10**9 + 7

def rangeProductQueries(n, queries):
    # Build the powers array from n's binary representation.
    powers = []
    bit = 0
    while n > 0:
        if n & 1:
            # Append 2^bit, which is the corresponding power of 2.
            powers.append(1 << bit)
        bit += 1
        n >>= 1

    # Build prefix product array for fast range multiplication.
    prefix = [1]  # prefix[0] is 1 (multiplicative identity).
    for value in powers:
        prefix.append((prefix[-1] * value) % MOD)
    
    # Prepare answers for each query.
    ans = []
    for left, right in queries:
        # Compute modular inverse of prefix[left]
        inv = pow(prefix[left], MOD - 2, MOD)
        product = (prefix[right + 1] * inv) % MOD
        ans.append(product)
    return ans

# Example usage:
# n = 15, queries = [[0,1],[2,2],[0,3]] should output [2,4,64]
print(rangeProductQueries(15, [[0, 1], [2, 2], [0, 3]]))
← Back to All Questions