Range Product Queries of Powers

Problem Description

Given a positive integer n, there exists a 0-indexed array called powers, composed of the minimum number of powers of 2 that sum to n. The array is sorted in non-decreasing order, and there is only one way to form the array. You are also given a 0-indexed 2D integer array queries, where queries[i] = [left_i, right_i]. Each queries[i] represents a query where you have to find the product of all powers[j] with left_i <= j <= right_i. Return an array answers, equal in length to queries, where answers[i] is the answer to the i-th query. Since the answer to the i-th query may be too large, each answers[i] should be returned modulo 10^9 + 7.

Key Insights

• The powers array is constructed from the binary representation of n, where each bit represents a power of 2.
• The length of the powers array can be determined by counting the number of set bits in n.
• Each query can be answered efficiently using prefix products to avoid recalculating products for overlapping ranges.
• The modulo operation is crucial to prevent overflow and ensure results fit within standard data types.

Space and Time Complexity

Time Complexity: O(m + q), where m is the number of powers and q is the number of queries.
Space Complexity: O(m), where m is the number of powers.

Solution

To solve the problem, we will:

1. Construct the powers array by determining the powers of 2 that sum to n using its binary representation.
2. Precompute the prefix products of the powers array to allow for efficient range product calculations.
3. For each query, use the prefix products to compute the product of the specified range in constant time.

The data structure used is an array for powers and an additional array for prefixProducts.

Code Solutions