Om Shree

Posted on Aug 11

🈵Beginners guide to "2438. Range Product Queries of Powers"(C++ | JavaScript | Python)

#cpp #javascript #python #beginners

You are given a positive integer n. There exists a unique array called powers that consists of the minimum number of powers of 2 (i.e., 1, 2, 4, 8, ...) that sum up to n.

For example:

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

This powers array is sorted in non-decreasing order, and it is derived directly from the binary representation of n.

You are also given a list of queries. Each query specifies a range in the powers array, and you are to compute the product of all values in that range, modulo 10^9 + 7.

Intuition

The key is to understand that powers contains the positions of the 1s in the binary representation of n. Each 1 at position i contributes a power 2^i.

Instead of directly constructing powers, we can work with their exponents (the indices of the set bits), and then precompute prefix sums over these exponents.

We use the formula:

Product of 2^e1 * 2^e2 * ... * 2^ek = 2^(e1 + e2 + ... + ek)

This allows us to:

Store only the exponents (positions of the 1s in the binary representation)
Compute prefix sums over those exponents
Use fast exponentiation with modulo to compute results efficiently

Approach

Use __builtin_ctz(n) to find the lowest set bit in n, remove it, and store its exponent.
Maintain a prefix sum of the exponents for fast range sum computation.
Precompute powers of 2 modulo $10^9 + 7$ up to the total sum of exponents.
For each query [left, right], compute the total exponent e = sum(right) - sum(left-1), then return 2^e % MOD.

C++ Code

class Solution {
public:
    vector<int> productQueries(int n, const vector<vector<int>>& queries) {
        constexpr int MOD = 1000000007;

        // Step 1: Extract exponent positions of set bits in n
        vector<int> prefix {0};
        while (n) {
            int j = __builtin_ctz(n); // Count trailing zeroes (position of lowest set bit)
            prefix.push_back(prefix.back() + j);
            n -= 1 << j;
        }

        // Step 2: Precompute powers of 2 up to max sum of exponents
        int maxExp = prefix.back();
        vector<int> pow2 {1}; pow2.reserve(maxExp + 1);
        for (int i = 1; i <= maxExp; ++i)
            pow2.push_back((pow2.back() << 1) % MOD);

        // Step 3: Process queries
        vector<int> result; result.reserve(queries.size());
        for (const auto& q : queries) {
            int totalExp = prefix[q[1] + 1] - prefix[q[0]];
            result.push_back(pow2[totalExp]);
        }

        return result;
    }
};

JavaScript Version

var productQueries = function(n, queries) {
    const MOD = 1e9 + 7;

    const prefix = [0];
    for (let i = 0; n > 0; ) {
        const j = Math.clz32(n & -n) ^ 31;
        prefix.push(prefix[prefix.length - 1] + j);
        n -= 1 << j;
    }

    const maxExp = prefix[prefix.length - 1];
    const pow2 = [1];
    for (let i = 1; i <= maxExp; i++) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }

    return queries.map(([l, r]) => {
        const totalExp = prefix[r + 1] - prefix[l];
        return pow2[totalExp];
    });
};

Python Version

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

        # Step 1: Extract exponents of powers of 2 in binary representation
        prefix = [0]
        i = 0
        while n:
            if n & 1:
                prefix.append(prefix[-1] + i)
            n >>= 1
            i += 1

        # Step 2: Precompute powers of 2 modulo MOD
        max_exp = prefix[-1]
        pow2 = [1]
        for _ in range(max_exp):
            pow2.append((pow2[-1] * 2) % MOD)

        # Step 3: Answer queries
        return [pow2[prefix[r + 1] - prefix[l]] for l, r in queries]

Time and Space Complexity

Time Complexity:

Building the powers array from n: O(log n)
Precomputing powers of 2: O(log n)
Processing q queries: O(q)

Overall: O(q + log n)

Space Complexity:

Prefix sum array: O(log n)
Precomputed power table: O(log n)
Output array: O(q)

Final Thoughts

This problem rewards understanding of bit manipulation and efficient exponentiation. By working with the exponents rather than actual values, and by using prefix sums, we significantly reduce the complexity of handling large queries. The approach balances clarity and performance without needing to manipulate digits or build the full array of powers directly.

DEV Community