2438. Range Product Queries of Powers

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] = [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 109 + 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 109 + 7 is the same, so [2] is returned.

 

Constraints:

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

Solutions

Solution 1: Bit Manipulation + Simulation

We can use bit manipulation (lowbit) to obtain the \(\textit{powers}\) array, and then use simulation to find the answer for each query.

First, for a given positive integer \(n\), we can quickly obtain the value corresponding to the lowest bit \(1\) in the binary representation through \(n \& -n\), which is the minimum power of \(2\) factor of the current number. By repeatedly performing this operation on \(n\) and subtracting this value, we can sequentially obtain all the powers of \(2\) corresponding to the set bits, forming the \(\textit{powers}\) array. This array is in increasing order, and its length equals the number of \(1\)s in the binary representation of \(n\).

Next, we need to process each query. For the current query \((l, r)\), we need to calculate

\[ \textit{answers}[i] = \prod_{j=l}^{r} \textit{powers}[j] \]

where \(\textit{answers}[i]\) is the answer to the \(i\)-th query. Since the query results can be very large, we need to take modulo \(10^9 + 7\) for each answer.

The time complexity is \(O(m \times \log n)\), where \(m\) is the length of the array \(\textit{queries}\). Ignoring the space consumption of the answer, the space complexity is \(O(\log n)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        powers = []
        while n:
            x = n & -n
            powers.append(x)
            n -= x
        mod = 10**9 + 7
        ans = []
        for l, r in queries:
            x = 1
            for i in range(l, r + 1):
                x = x * powers[i] % mod
            ans.append(x)
        return ans

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        int[] powers = new int[Integer.bitCount(n)];
        for (int i = 0; n > 0; ++i) {
            int x = n & -n;
            powers[i] = x;
            n -= x;
        }
        int m = queries.length;
        int[] ans = new int[m];
        final int mod = (int) 1e9 + 7;
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            long x = 1;
            for (int j = l; j <= r; ++j) {
                x = x * powers[j] % mod;
            }
            ans[i] = (int) x;
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> powers;
        while (n) {
            int x = n & -n;
            powers.push_back(x);
            n -= x;
        }
        vector<int> ans;
        const int mod = 1e9 + 7;
        for (const auto& q : queries) {
            int l = q[0], r = q[1];
            long long x = 1;
            for (int j = l; j <= r; ++j) {
                x = x * powers[j] % mod;
            }
            ans.push_back(x);
        }
        return ans;
    }
};

func productQueries(n int, queries [][]int) []int {
    var powers []int
    for n > 0 {
        x := n & -n
        powers = append(powers, x)
        n -= x
    }
    const mod = 1_000_000_007
    ans := make([]int, 0, len(queries))
    for _, q := range queries {
        l, r := q[0], q[1]
        x := 1
        for j := l; j <= r; j++ {
            x = x * powers[j] % mod
        }
        ans = append(ans, x)
    }
    return ans
}

function productQueries(n: number, queries: number[][]): number[] {
    const powers: number[] = [];
    while (n > 0) {
        const x = n & -n;
        powers.push(x);
        n -= x;
    }
    const mod = 1_000_000_007;
    const ans: number[] = [];
    for (const [l, r] of queries) {
        let x = 1;
        for (let j = l; j <= r; j++) {
            x = (x * powers[j]) % mod;
        }
        ans.push(x);
    }
    return ans;
}

impl Solution {
    pub fn product_queries(mut n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut powers = Vec::new();
        while n > 0 {
            let x = n & -n;
            powers.push(x);
            n -= x;
        }
        let modulo = 1_000_000_007;
        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let l = q[0] as usize;
            let r = q[1] as usize;
            let mut x: i64 = 1;
            for j in l..=r {
                x = x * powers[j] as i64 % modulo;
            }
            ans.push(x as i32);
        }
        ans
    }
}

Comments