2438. Range Product Queries of Powers

[mah-shamim]

Topics: Array, Bit Manipulation, Prefix Sum, Biweekly Contest 89

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] = [lefti, righti]. Each queries[i] represents a query where you have to find the product of all powers[j] with lefti <= j <= righti.

Return an array answers, equal in length to queries, where answers[i] is the answer to the ith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 109 + 7.

Example 1:

• Input: n = 15, queries = [[0,1],[2,2],[0,3]]
• Output: [2,4,64]
• Explanation:
  For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size.
  Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2.
  Answer to 2nd query: powers[2] = 4.
  Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64.
  Each answer modulo 10⁹ + 7 yields the same answer, so [2,4,64] is returned.

Example 2:

• Input: n = 2, queries = [[0,0]]
• Output: [2]
• Explanation:
  For n = 2, powers = [2].
  The answer to the only query is powers[0] = 2. The answer modulo 10⁹ + 7 is the same, so [2] is returned.

Constraints:

• 1 <= n <= 109
• 1 <= queries.length <= 105
• 0 <= starti <= endi < powers.length

Hint:

1. The powers array can be created using the binary representation of n.
2. Once powers is formed, the products can be taken using brute force.

[mah-shamim]

We need to efficiently answer multiple range product queries on an array derived from the binary representation of a given positive integer n. The array consists of the minimum number of distinct powers of 2 that sum to n, sorted in non-decreasing order. Each query requires computing the product of elements within a specified range in this array, modulo 10⁹ + 7.

Approach

1. Generate Powers Array:

   • The powers array is constructed by decomposing n into its binary representation. Each set bit in the binary form of n corresponds to a power of 2. For example, if n is 15 (binary 1111), the powers array will be [1, 2, 4, 8].
   • We iterate through each bit of n from the least significant bit (LSB) to the most significant bit (MSB). For each set bit, we include the corresponding power of 2 in the array. This ensures the array is sorted in non-decreasing order.

2. Process Queries:

   • For each query [left, right], compute the product of elements in the powers array from index left to right.
   • To handle large numbers, each multiplication is followed by taking modulo 10⁹ + 7. This prevents integer overflow and ensures results fit within standard data types.

Let's implement this solution in PHP: 2438. Range Product Queries of Powers

<?php
/**
 * @param Integer $n
 * @param Integer[][] $queries
 * @return Integer[]
 */
function productQueries($n, $queries) {
    $mod = 1000000007;
    $powers = [];
    $current = 1;
    $temp = $n;
    while ($temp) {
        if ($temp & 1) {
            $powers[] = $current;
        }
        $temp = $temp >> 1;
        $current *= 2;
    }

    $ans = [];
    foreach ($queries as $q) {
        $l = $q[0];
        $r = $q[1];
        $product = 1;
        for ($i = $l; $i <= $r; $i++) {
            $product = ($product * $powers[$i]) % $mod;
        }
        $ans[] = $product;
    }
    return $ans;
}

// Test cases
$n = 15;
$queries = [[0,1],[2,2],[0,3]];
print_r(productQueries($n, $queries)); // Output: [2, 4, 64]

$n = 2;
$queries = [[0,0]];
print_r(productQueries($n, $queries)); // Output: [2]
?>

Explanation:

1. Generating the Powers Array:

   • We start with current = 1 (representing 2⁰) and process each bit of n from LSB to MSB.
   • For each bit, if it is set ($temp & 1 is true), we add current to the powers array.
   • We then right-shift temp to process the next bit and double current to move to the next power of 2.

2. Answering Queries:

   • For each query, we initialize product to 1.
   • We iterate from the start index l to the end index r of the query, multiplying each element in the powers array within this range.
   • After each multiplication, we take modulo 10⁹ + 7 to keep the intermediate results manageable and avoid overflow.
   • The final product for each query is stored in the ans array, which is returned after processing all queries.

This approach efficiently handles the constraints by leveraging the binary decomposition of n to create a compact powers array and processes each query in linear time relative to the length of the query range, which is optimal given the small size of the powers array (up to 31 elements for n ≤ 10⁹). The modulo operation ensures that all operations remain within feasible computational limits.

[basharul-siddike]

Thanks for solving the problem of "Range Product Queries of Powers"

[mah-shamim]

Thanks