Find Products of Elements of Big Array
HardUpdated: Aug 2, 2025
Practice on:
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
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 <= 500queries[i].length == 30 <= queries[i][0] <= queries[i][1] <= 10151 <= 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
- For each integer
i, compute its powerful array (powers of two for each set bit). - Maintain a running total of the length of the concatenated array to map indices to the corresponding number and bit.
- For each query
[fromi, toi, modi]:- Use binary search to find which numbers cover the
fromiandtoipositions. - 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.
- Use binary search to find which numbers cover the
- Return the answer for each query.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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), whereQis the number of queries andNis the maximum index in big_nums, due to binary search and bit operations. - 🧺 Space complexity:
O(N), for the prefix sum array.