Problem

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.

num Binary Representation powerful array
1 0000 1 [1]
8 0 1 000 [8]
10 0 1 0 1 0 [2, 8]
13 0 11 0 1 [1, 4, 8]
23 1 0 111 [1, 2, 4, 16]

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [_1_ , _2_ , _1, 2_ , _4_ , _1, 4_ , _2, 4_ , _1, 2, 4_ , _8_ , ...].

You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ...* big_nums[toi]) % modi.

Return an integer array answer such that answer[i] is the answer to the ith query.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: queries = [[1,3,7]]

Output: [4]

Explanation:

There is one query.

`big_nums[1..3] = [2,1,2]`. The product of them is 4. The result is `4 % 7 =
4.`

Example 2

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


Input: queries = [[2,5,3],[7,7,4]]

Output: [2,2]

Explanation:

There are two queries.

First query: `big_nums[2..5] = [1,2,4,1]`. The product of them is 8. The
result is `8 % 3 = 2`.

Second query: `big_nums[7] = 2`. The result is `2 % 4 = 2`.

Constraints

  • 1 <= queries.length <= 500
  • queries[i].length == 3
  • 0 <= queries[i][0] <= queries[i][1] <= 1015
  • 1 <= queries[i][2] <= 10^5

Solution

Method 1 – Bit Manipulation and Prefix Products

Intuition

The powerful array for each integer is the set of powers of two corresponding to the set bits in its binary representation. The concatenated array grows quickly, so we need to efficiently map a query index to the corresponding number and bit. We can precompute the lengths and use prefix products for fast queries.

Approach

  1. For each integer i, compute its powerful array (powers of two for each set bit).
  2. Maintain a running total of the length of the concatenated array to map indices to the corresponding number and bit.
  3. For each query [fromi, toi, modi]:
    • Use binary search to find which numbers cover the fromi and toi positions.
    • For each number in the range, determine which bits (powers of two) are included in the query range.
    • Multiply the relevant powers of two modulo modi.
  4. Return the answer for each query.

Code

 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
34
35

class Solution {
public:
    vector<int> findProducts(vector<vector<int>>& queries) {
        vector<int> lens = {0};
        for (int i = 1; lens.back() < 1e6; ++i) {
            lens.push_back(lens.back() + __builtin_popcount(i));
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1], mod = q[2];
            long long res = 1;
            int li = lower_bound(lens.begin(), lens.end(), l) - lens.begin();
            int ri = lower_bound(lens.begin(), lens.end(), r) - lens.begin();
            int lp = l - lens[li-1], rp = r - lens[ri-1];
            if (li == ri) {
                vector<int> bits;
                for (int b = 0; b < 32; ++b) if ((li >> b) & 1) bits.push_back(1 << b);
                for (int i = lp-1; i < rp; ++i) res = res * bits[i] % mod;
            } else {
                vector<int> bitsl, bitsr;
                for (int b = 0; b < 32; ++b) {
                    if ((li >> b) & 1) bitsl.push_back(1 << b);
                    if ((ri >> b) & 1) bitsr.push_back(1 << b);
                }
                for (int i = lp-1; i < bitsl.size(); ++i) res = res * bitsl[i] % mod;
                for (int num = li+1; num < ri; ++num) {
                    for (int b = 0; b < 32; ++b) if ((num >> b) & 1) res = res * (1 << b) % mod;
                }
                for (int i = 0; i < rp; ++i) res = res * bitsr[i] % mod;
            }
            ans.push_back(res);
        }
        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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

func findProducts(queries [][]int) []int {
    lens := []int{0}
    for i := 1; lens[len(lens)-1] < 1e6; i++ {
        lens = append(lens, lens[len(lens)-1]+bits.OnesCount(uint(i)))
    }
    ans := []int{}
    for _, q := range queries {
        l, r, mod := q[0], q[1], q[2]
        res := 1
        li := sort.SearchInts(lens, l)
        ri := sort.SearchInts(lens, r)
        lp, rp := l-lens[li-1], r-lens[ri-1]
        if li == ri {
            bits := []int{}
            for b := 0; b < 32; b++ {
                if (li>>b)&1 == 1 {
                    bits = append(bits, 1<<b)
                }
            }
            for i := lp - 1; i < rp; i++ {
                res = res * bits[i] % mod
            }
        } else {
            bitsl, bitsr := []int{}, []int{}
            for b := 0; b < 32; b++ {
                if (li>>b)&1 == 1 {
                    bitsl = append(bitsl, 1<<b)
                }
                if (ri>>b)&1 == 1 {
                    bitsr = append(bitsr, 1<<b)
                }
            }
            for i := lp - 1; i < len(bitsl); i++ {
                res = res * bitsl[i] % mod
            }
            for num := li + 1; num < ri; num++ {
                for b := 0; b < 32; b++ {
                    if (num>>b)&1 == 1 {
                        res = res * (1 << b) % mod
                    }
                }
            }
            for i := 0; i < rp; i++ {
                res = res * bitsr[i] % mod
            }
        }
        ans = append(ans, res)
    }
    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
34
35
36
37

class Solution {
    public List<Integer> findProducts(int[][] queries) {
        List<Integer> lens = new ArrayList<>();
        lens.add(0);
        for (int i = 1; lens.get(lens.size()-1) < 1e6; i++) {
            lens.add(lens.get(lens.size()-1) + Integer.bitCount(i));
        }
        List<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            int l = q[0], r = q[1], mod = q[2];
            long res = 1;
            int li = Collections.binarySearch(lens, l);
            if (li < 0) li = -li - 1;
            int ri = Collections.binarySearch(lens, r);
            if (ri < 0) ri = -ri - 1;
            int lp = l - lens.get(li-1), rp = r - lens.get(ri-1);
            if (li == ri) {
                List<Integer> bits = new ArrayList<>();
                for (int b = 0; b < 32; b++) if (((li >> b) & 1) == 1) bits.add(1 << b);
                for (int i = lp-1; i < rp; i++) res = res * bits.get(i) % mod;
            } else {
                List<Integer> bitsl = new ArrayList<>(), bitsr = new ArrayList<>();
                for (int b = 0; b < 32; b++) {
                    if (((li >> b) & 1) == 1) bitsl.add(1 << b);
                    if (((ri >> b) & 1) == 1) bitsr.add(1 << b);
                }
                for (int i = lp-1; i < bitsl.size(); i++) res = res * bitsl.get(i) % mod;
                for (int num = li+1; num < ri; num++) {
                    for (int b = 0; b < 32; b++) if (((num >> b) & 1) == 1) res = res * (1 << b) % mod;
                }
                for (int i = 0; i < rp; i++) res = res * bitsr.get(i) % mod;
            }
            ans.add((int)res);
        }
        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

class Solution {
    fun findProducts(queries: Array<IntArray>): List<Int> {
        val lens = mutableListOf(0)
        while (lens.last() < 1e6) lens.add(lens.last() + Integer.bitCount(lens.size))
        val ans = mutableListOf<Int>()
        for (q in queries) {
            val (l, r, mod) = q
            var res = 1L
            var li = lens.binarySearch(l)
            if (li < 0) li = -li - 1
            var ri = lens.binarySearch(r)
            if (ri < 0) ri = -ri - 1
            val lp = l - lens[li-1]
            val rp = r - lens[ri-1]
            if (li == ri) {
                val bits = (0..31).filter { (li shr it) and 1 == 1 }.map { 1 shl it }
                for (i in lp-1 until rp) res = res * bits[i] % mod
            } else {
                val bitsl = (0..31).filter { (li shr it) and 1 == 1 }.map { 1 shl it }
                val bitsr = (0..31).filter { (ri shr it) and 1 == 1 }.map { 1 shl it }
                for (i in lp-1 until bitsl.size) res = res * bitsl[i] % mod
                for (num in li+1 until ri) for (b in 0..31) if ((num shr b) and 1 == 1) res = res * (1 shl b) % mod
                for (i in 0 until rp) res = res * bitsr[i] % mod
            }
            ans.add(res.toInt())
        }
        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

class Solution:
    def findProducts(self, queries: list[list[int]]) -> list[int]:
        lens = [0]
        i = 1
        while lens[-1] < 10**6:
            lens.append(lens[-1] + bin(i).count('1'))
            i += 1
        ans = []
        for l, r, mod in queries:
            li = next(i for i in range(len(lens)) if lens[i] >= l)
            ri = next(i for i in range(len(lens)) if lens[i] >= r)
            lp = l - lens[li-1]
            rp = r - lens[ri-1]
            res = 1
            if li == ri:
                bits = [1 << b for b in range(32) if (li >> b) & 1]
                for i in range(lp-1, rp):
                    res = res * bits[i] % mod
            else:
                bitsl = [1 << b for b in range(32) if (li >> b) & 1]
                bitsr = [1 << b for b in range(32) if (ri >> b) & 1]
                for i in range(lp-1, len(bitsl)):
                    res = res * bitsl[i] % mod
                for num in range(li+1, ri):
                    for b in range(32):
                        if (num >> b) & 1:
                            res = res * (1 << b) % mod
                for i in range(rp):
                    res = res * bitsr[i] % mod
            ans.append(res)
        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
34
35
36
37
38
39
40
41
42
43

impl Solution {
    pub fn find_products(queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut lens = vec![0];
        let mut i = 1;
        while *lens.last().unwrap() < 1_000_000 {
            lens.push(lens.last().unwrap() + i.count_ones() as i32);
            i += 1;
        }
        let mut ans = vec![];
        for q in queries.iter() {
            let (l, r, m) = (q[0], q[1], q[2]);
            let li = lens.iter().position(|&x| x >= l).unwrap();
            let ri = lens.iter().position(|&x| x >= r).unwrap();
            let lp = l - lens[li-1];
            let rp = r - lens[ri-1];
            let mut res = 1i64;
            if li == ri {
                let bits: Vec<i64> = (0..32).filter(|&b| (li >> b) & 1 == 1).map(|b| 1 << b).collect();
                for i in (lp-1)..rp {
                    res = res * bits[i as usize] % m as i64;
                }
            } else {
                let bitsl: Vec<i64> = (0..32).filter(|&b| (li >> b) & 1 == 1).map(|b| 1 << b).collect();
                let bitsr: Vec<i64> = (0..32).filter(|&b| (ri >> b) & 1 == 1).map(|b| 1 << b).collect();
                for i in (lp-1)..(bitsl.len() as i32) {
                    res = res * bitsl[i as usize] % m as i64;
                }
                for num in (li+1)..ri {
                    for b in 0..32 {
                        if (num >> b) & 1 == 1 {
                            res = res * (1 << b) % m as i64;
                        }
                    }
                }
                for i in 0..rp {
                    res = res * bitsr[i as usize] % m as i64;
                }
            }
            ans.push(res as i32);
        }
        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

class Solution {
    findProducts(queries: number[][]): number[] {
        const lens: number[] = [0];
        let i = 1;
        while (lens[lens.length-1] < 1e6) lens.push(lens[lens.length-1] + i.toString(2).split('1').length-1), i++;
        const ans: number[] = [];
        for (const [l, r, mod] of queries) {
            let li = lens.findIndex(x => x >= l);
            let ri = lens.findIndex(x => x >= r);
            const lp = l - lens[li-1];
            const rp = r - lens[ri-1];
            let res = 1;
            if (li === ri) {
                const bits = [];
                for (let b = 0; b < 32; b++) if ((li >> b) & 1) bits.push(1 << b);
                for (let i = lp-1; i < rp; i++) res = res * bits[i] % mod;
            } else {
                const bitsl = [], bitsr = [];
                for (let b = 0; b < 32; b++) {
                    if ((li >> b) & 1) bitsl.push(1 << b);
                    if ((ri >> b) & 1) bitsr.push(1 << b);
                }
                for (let i = lp-1; i < bitsl.length; i++) res = res * bitsl[i] % mod;
                for (let num = li+1; num < ri; num++) for (let b = 0; b < 32; b++) if ((num >> b) & 1) res = res * (1 << b) % mod;
                for (let i = 0; i < rp; i++) res = res * bitsr[i] % mod;
            }
            ans.push(res);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(Q * log N), where Q is the number of queries and N is the maximum index in big_nums, due to binary search and bit operations.
  • 🧺 Space complexity: O(N), for the prefix sum array.