Problem

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 arrayanswers , equal in length toqueries , whereanswers[i]is the answer to theith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    
    
    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^9 + 7 yields the same answer, so [2,4,64] is returned.

Example 2

1
2
3
4
5
6
7
8
9


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

Constraints

  • 1 <= n <= 10^9
  • 1 <= queries.length <= 10^5
  • 0 <= starti <= endi < powers.length

Solution

Method 1 – Bit Manipulation and Prefix Product

Intuition

The array powers is the list of powers of 2 that sum to n, i.e., the set bits in n as powers of 2. For each query, the product of a subarray is just the product of the corresponding powers, which is another power of 2. We can precompute prefix products for fast queries.

Approach

  1. Extract all set bits of n and store their corresponding powers of 2 in a list powers (from least to most significant bit).
  2. Compute prefix products modulo 10^9+7.
  3. For each query [l, r], compute the product as prefix[r+1] // prefix[l] (or using modular inverse for modulo division).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> p;
        for (int i = 0; i < 32; ++i) if (n & (1 << i)) p.push_back(1 << i);
        int m = p.size(), mod = 1e9+7;
        vector<long long> pre(m+1, 1);
        for (int i = 0; i < m; ++i) pre[i+1] = pre[i] * p[i] % mod;
        vector<int> ans;
        auto modinv = [&](long long a) {
            long long res = 1, b = mod-2;
            while (b) { if (b&1) res = res*a%mod; a = a*a%mod; b>>=1; }
            return res;
        };
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            ans.push_back(pre[r+1] * modinv(pre[l]) % mod);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func productQueries(n int, queries [][]int) []int {
    mod := int(1e9+7)
    p := []int{}
    for i := 0; i < 32; i++ {
        if n&(1<<i) > 0 {
            p = append(p, 1<<i)
        }
    }
    m := len(p)
    pre := make([]int, m+1)
    pre[0] = 1
    for i := 0; i < m; i++ {
        pre[i+1] = pre[i] * p[i] % mod
    }
    modinv := func(a int) int {
        res, b := 1, mod-2
        aa := a
        for b > 0 {
            if b&1 == 1 {
                res = res * aa % mod
            }
            aa = aa * aa % mod
            b >>= 1
        }
        return res
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        ans[i] = pre[r+1] * modinv(pre[l]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        List<Integer> p = new ArrayList<>();
        for (int i = 0; i < 32; ++i) if ((n & (1 << i)) > 0) p.add(1 << i);
        int m = p.size(), mod = (int)1e9+7;
        long[] pre = new long[m+1];
        pre[0] = 1;
        for (int i = 0; i < m; ++i) pre[i+1] = pre[i] * p.get(i) % mod;
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = (int)(pre[r+1] * powmod(pre[l], mod-2, mod) % mod);
        }
        return ans;
    }
    private long powmod(long a, int b, int mod) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun productQueries(n: Int, queries: Array<IntArray>): IntArray {
        val p = mutableListOf<Int>()
        for (i in 0 until 32) if ((n and (1 shl i)) > 0) p.add(1 shl i)
        val m = p.size; val mod = 1_000_000_007
        val pre = LongArray(m+1) { 1L }
        for (i in 0 until m) pre[i+1] = pre[i] * p[i] % mod
        fun modinv(a: Long): Long {
            var res = 1L; var b = mod-2; var aa = a
            while (b > 0) {
                if (b and 1 == 1) res = res * aa % mod
                aa = aa * aa % mod; b = b shr 1
            }
            return res
        }
        return queries.map { (l, r) -> (pre[r+1] * modinv(pre[l]) % mod).toInt() }.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        mod = 10**9 + 7
        p = [1 << i for i in range(32) if (n >> i) & 1]
        pre = [1]
        for x in p:
            pre.append(pre[-1] * x % mod)
        def modinv(a: int) -> int:
            return pow(a, mod-2, mod)
        return [(pre[r+1] * modinv(pre[l])) % mod for l, r in queries]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn product_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let modn = 1_000_000_007i64;
        let mut p = vec![];
        for i in 0..32 {
            if (n >> i) & 1 == 1 { p.push(1 << i); }
        }
        let mut pre = vec![1i64];
        for &x in &p { pre.push(pre.last().unwrap() * (x as i64) % modn); }
        let modinv = |a: i64| -> i64 {
            let mut res = 1i64; let mut b = modn-2; let mut aa = a;
            while b > 0 {
                if b & 1 == 1 { res = res * aa % modn; }
                aa = aa * aa % modn; b >>= 1;
            }
            res
        };
        queries.iter().map(|q| (pre[q[1] as usize + 1] * modinv(pre[q[0] as usize]) % modn) as i32).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    productQueries(n: number, queries: number[][]): number[] {
        const mod = 1e9+7;
        const p: number[] = [];
        for (let i = 0; i < 32; ++i) if ((n >> i) & 1) p.push(1 << i);
        const m = p.length;
        const pre: number[] = [1];
        for (let i = 0; i < m; ++i) pre.push(pre[pre.length-1] * p[i] % mod);
        const modinv = (a: number): number => {
            let res = 1, b = mod-2, aa = a;
            while (b > 0) {
                if (b & 1) res = res * aa % mod;
                aa = aa * aa % mod; b >>= 1;
            }
            return res;
        };
        return queries.map(([l, r]) => pre[r+1] * modinv(pre[l]) % mod);
    }
}

Complexity

  • ⏰ Time complexity: O(Q + log n), where Q is the number of queries. Extracting powers is O(log n), prefix computation is O(log n), and each query is O(1).
  • 🧺 Space complexity: O(log n), for storing the powers and prefix products.