# 3145. Find Products of Elements of Big Array

## Description

A powerful array for an integer x is the shortest sorted array of powers of two that sum up to x. For example, the powerful array for 11 is [1, 2, 8].

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so forth. Thus, big_nums starts 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.

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 remainder of 4 under 7 is 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 remainder of 8 under 3 is 2.

Second query: big_nums[7] = 2. The remainder of 2 under 4 is 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

• 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;
}
}

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;
}
}

• 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;
}
}

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);
ans[i] = static_cast<int>(qpow(2, power, mod));
}
return ans;
}
};

• 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

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]

• 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 {
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
}
}

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
}