Skip to content

3145. Find Products of Elements of Big Array

Description

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 00001 [1]
8 01000 [8]
10 01010 [2, 8]
13 01101 [1, 4, 8]
23 10111 [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.

 

Example 1:

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:

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] <= 105

Solutions

Solution 1: Binary Search + Bit Manipulation

The continuous positive integer numbers correspond to the strong integer array, forming the array $\textit{bignums}$. The problem requires us to find the result of the product of the subarray $\textit{bignums}[\textit{left}..\textit{right}]$ modulo $\textit{mod}$ for each query $[\textit{left}, \textit{right}, \textit{mod}]$. Since each element of the subarray is a power of 2, this is equivalent to finding the sum of the powers $\textit{power}$ of the subarray, and then calculating $2^{\textit{power}} \bmod \textit{mod}$. For example, for the subarray $[1, 4, 8]$, i.e., $[2^0, 2^2, 2^3]$, the sum of the powers is $0 + 2 + 3 = 5$, so $2^5 \bmod \textit{mod}$ is the result we need.

Therefore, we can convert $\textit{bignums}$ into an array of powers. For example, for the subarray $[1, 4, 8]$, we convert it to $[0, 2, 3]$. Thus, the problem is transformed into finding the sum of the subarray of powers, i.e., $\textit{power} = \textit{f}(\textit{right} + 1) - \textit{f}(\textit{left})$, where $\textit{f}(i)$ represents the sum of the powers of $\textit{bignums}[0..i)$, which is the prefix sum.

Next, we calculate the value of $\textit{f}(i)$ based on the index $i$. We can use binary search to find the largest number whose strong array length is less than $i$, and then calculate the sum of the powers of the remaining numbers.

According to the problem description, we list the strong integers for numbers $0..14$:

$\textit{nums}$ 8($2^3$) 4($2^2$) 2($2^1$) ($2^0$)
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0

By dividing the numbers into different colors according to the interval $[2^i, 2^{i+1}-1]$, we can see that the numbers in the interval $[2^i, 2^{i+1}-1]$ are equivalent to adding $2^i$ to each number in the interval $[0, 2^i-1]$. Based on this pattern, we can calculate the total number of strong arrays $\textit{cnt}[i]$ and the sum of powers $\textit{s}[i]$ for the first $i$ groups of numbers in $\textit{bignums}$.

Next, for any number, we consider how to calculate the number of strong arrays and the sum of powers. We can use the binary method, calculating from the highest bit. For example, for the number $13 = 2^3 + 2^2 + 2^0$, the result of the first $2^3$ numbers can be obtained from $\textit{cnt}[3]$ and $\textit{s}[3]$, and the result of the remaining $[2^3, 13]$ is equivalent to adding $3$ to all numbers in $[0, 13-2^3]$, i.e., $[0, 5]$. The problem is transformed into calculating the number of strong arrays and the sum of powers for $[0, 5]$. In this way, we can calculate the number of strong arrays and the sum of powers for any number.

Finally, based on the value of $\textit{power}$, we use the fast exponentiation method to calculate the result of $2^{\textit{power}} \bmod \textit{mod}$.

The time complexity is $O(q \times \log M)$, and the space complexity is $O(\log M)$. Here, $q$ is the number of queries, and $M$ is the upper bound of the number, with $M \le 10^{15}$ in this problem.

 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
m = 50
cnt = [0] * (m + 1)
s = [0] * (m + 1)
p = 1
for i in range(1, m + 1):
    cnt[i] = cnt[i - 1] * 2 + p
    s[i] = s[i - 1] * 2 + p * (i - 1)
    p *= 2


def num_idx_and_sum(x: int) -> tuple:
    idx = 0
    total_sum = 0
    while x:
        i = x.bit_length() - 1
        idx += cnt[i]
        total_sum += s[i]
        x -= 1 << i
        total_sum += (x + 1) * i
        idx += x + 1
    return (idx, total_sum)


def f(i: int) -> int:
    l, r = 0, 1 << m
    while l < r:
        mid = (l + r + 1) >> 1
        idx, _ = num_idx_and_sum(mid)
        if idx < i:
            l = mid
        else:
            r = mid - 1

    total_sum = 0
    idx, total_sum = num_idx_and_sum(l)
    i -= idx
    x = l + 1
    for _ in range(i):
        y = x & -x
        total_sum += y.bit_length() - 1
        x -= y
    return total_sum


class Solution:
    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        return [pow(2, f(right + 1) - f(left), mod) for left, right, mod in queries]

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    private static final int M = 50;
    private static final long[] cnt = new long[M + 1];
    private static final long[] s = new long[M + 1];

    static {
        long p = 1;
        for (int i = 1; i <= M; i++) {
            cnt[i] = cnt[i - 1] * 2 + p;
            s[i] = s[i - 1] * 2 + p * (i - 1);
            p *= 2;
        }
    }

    private static long[] numIdxAndSum(long x) {
        long idx = 0;
        long totalSum = 0;
        while (x > 0) {
            int i = Long.SIZE - Long.numberOfLeadingZeros(x) - 1;
            idx += cnt[i];
            totalSum += s[i];
            x -= 1L << i;
            totalSum += (x + 1) * i;
            idx += x + 1;
        }
        return new long[] {idx, totalSum};
    }

    private static long f(long i) {
        long l = 0;
        long r = 1L << M;
        while (l < r) {
            long mid = (l + r + 1) >> 1;
            long[] idxAndSum = numIdxAndSum(mid);
            long idx = idxAndSum[0];
            if (idx < i) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        long[] idxAndSum = numIdxAndSum(l);
        long totalSum = idxAndSum[1];
        long idx = idxAndSum[0];
        i -= idx;
        long x = l + 1;
        for (int j = 0; j < i; j++) {
            long y = x & -x;
            totalSum += Long.numberOfTrailingZeros(y);
            x -= y;
        }
        return totalSum;
    }

    public int[] findProductsOfElements(long[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            long left = queries[i][0];
            long right = queries[i][1];
            long mod = queries[i][2];
            long power = f(right + 1) - f(left);
            ans[i] = qpow(2, power, mod);
        }
        return ans;
    }

    private int qpow(long a, long n, long mod) {
        long ans = 1 % mod;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans = ans * a % mod;
            }
            a = a * a % mod;
        }
        return (int) 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using ll = long long;
const int m = 50;
ll cnt[m + 1];
ll s[m + 1];
ll p = 1;

auto init = [] {
    cnt[0] = 0;
    s[0] = 0;
    for (int i = 1; i <= m; ++i) {
        cnt[i] = cnt[i - 1] * 2 + p;
        s[i] = s[i - 1] * 2 + p * (i - 1);
        p *= 2;
    }
    return 0;
}();

pair<ll, ll> numIdxAndSum(ll x) {
    ll idx = 0;
    ll totalSum = 0;
    while (x > 0) {
        int i = 63 - __builtin_clzll(x);
        idx += cnt[i];
        totalSum += s[i];
        x -= 1LL << i;
        totalSum += (x + 1) * i;
        idx += x + 1;
    }
    return make_pair(idx, totalSum);
}

ll f(ll i) {
    ll l = 0;
    ll r = 1LL << m;
    while (l < r) {
        ll mid = (l + r + 1) >> 1;
        auto idxAndSum = numIdxAndSum(mid);
        ll idx = idxAndSum.first;
        if (idx < i) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    auto idxAndSum = numIdxAndSum(l);
    ll totalSum = idxAndSum.second;
    ll idx = idxAndSum.first;
    i -= idx;
    ll x = l + 1;
    for (int j = 0; j < i; ++j) {
        ll y = x & -x;
        totalSum += __builtin_ctzll(y);
        x -= y;
    }
    return totalSum;
}

ll qpow(ll a, ll n, ll mod) {
    ll ans = 1 % mod;
    a = a % mod;
    while (n > 0) {
        if (n & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

class Solution {
public:
    vector<int> findProductsOfElements(vector<vector<ll>>& queries) {
        int n = queries.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ll left = queries[i][0];
            ll right = queries[i][1];
            ll mod = queries[i][2];
            ll power = f(right + 1) - f(left);
            if (power < 0) {
                power += mod;
            }
            ans[i] = static_cast<int>(qpow(2, power, 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
const m = 50

var cnt [m + 1]int64
var s [m + 1]int64
var p int64 = 1

func init() {
    cnt[0] = 0
    s[0] = 0
    for i := 1; i <= m; i++ {
        cnt[i] = cnt[i-1]*2 + p
        s[i] = s[i-1]*2 + p*(int64(i)-1)
        p *= 2
    }
}

func numIdxAndSum(x int64) (int64, int64) {
    var idx, totalSum int64
    for x > 0 {
        i := 63 - bits.LeadingZeros64(uint64(x))
        idx += cnt[i]
        totalSum += s[i]
        x -= 1 << i
        totalSum += (x + 1) * int64(i)
        idx += x + 1
    }
    return idx, totalSum
}

func f(i int64) int64 {
    l, r := int64(0), int64(1)<<m
    for l < r {
        mid := (l + r + 1) >> 1
        idx, _ := numIdxAndSum(mid)
        if idx < i {
            l = mid
        } else {
            r = mid - 1
        }
    }

    _, totalSum := numIdxAndSum(l)
    idx, _ := numIdxAndSum(l)
    i -= idx
    x := l + 1
    for j := int64(0); j < i; j++ {
        y := x & -x
        totalSum += int64(bits.TrailingZeros64(uint64(y)))
        x -= y
    }
    return totalSum
}

func qpow(a, n, mod int64) int64 {
    ans := int64(1) % mod
    a = a % mod
    for n > 0 {
        if n&1 == 1 {
            ans = (ans * a) % mod
        }
        a = (a * a) % mod
        n >>= 1
    }
    return ans
}

func findProductsOfElements(queries [][]int64) []int {
    ans := make([]int, len(queries))
    for i, q := range queries {
        left, right, mod := q[0], q[1], q[2]
        power := f(right+1) - f(left)
        ans[i] = int(qpow(2, power, mod))
    }
    return ans
}

Comments