LeetCode #3145 — HARD

Find Products of Elements of Big Array

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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] = [from_i, to_i, mod_i] you should calculate (big_nums[from_i] * big_nums[from_i + 1] * ... * big_nums[to_i]) % mod_i.

Return an integer array answer such that answer[i] is the answer to the i^th 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] <= 10¹⁵
1 <= queries[i][2] <= 10⁵

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Bit Manipulation

Example 1

[[1,3,7]]

Example 2

[[2,5,3],[7,7,4]]

Step 02

Core Insight

What unlocks the optimal approach

Find a way to calculate <code>f(n, i)</code> which is the total number of numbers in <code>[1, n]</code> when the <code>i<sup>th</sup></code> bit is set in <code>O(log(n))</code> time.
Use binary search to find the last number for each query (and there might be one “incomplete” number for the query).
Use a similar way to find the product (we only need to save the sum of exponents of power of <code>2</code>).

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
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;
    }
}

// Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
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
}

# Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
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]

// Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
/**
 * [3145] Find Products of Elements of Big Array
 */
pub struct Solution {}

// submission codes start here

impl Solution {
    pub fn find_products_of_elements(queries: Vec<Vec<i64>>) -> Vec<i32> {
        let mut result_array = Vec::with_capacity(queries.len());

        for query in queries {
            let (start, end) = (query[0] + 1, query[1] + 1);
            let left = Self::middle_check(start);
            let right = Self::middle_check(end);
            let mod_number = query[2];

            let mut result = 1;
            let mut pre = Self::count_one(left - 1);

            for i in 0..=60 {
                if (1 << i) & left != 0 {
                    pre += 1;

                    if pre >= start && pre <= end {
                        result = result * (1 << i) % mod_number;
                    }
                }
            }

            if right > left {
                let mut back = Self::count_one(right - 1);
                for i in 0..=60 {
                    if (1 << i) & right != 0 {
                        back += 1;

                        if back >= start && back <= end {
                            result = result * (1 << i) % mod_number;
                        }
                    }
                }
            }

            if right - left > 1 {
                let middle = Self::count_power(right - 1) - Self::count_power(left);

                result = result * Self::power_mod(2, middle, mod_number) % mod_number;
            }

            result_array.push(result);
        }

        result_array.iter().map(|x| *x as i32).collect()
    }

    fn middle_check(x: i64) -> i64 {
        let (mut left, mut right) = (1i64, 1e15 as i64);

        while left < right {
            let middle = (left + right) >> 1;
            if Self::count_one(middle) >= x {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        right
    }

    /// 计算小于等于x的数中数位1的和
    fn count_one(x: i64) -> i64 {
        let mut result = 0;
        let mut sum = 0;

        for i in (0..=60).rev() {
            if (1 << i) & x != 0 {
                result += sum * (1 << i);
                sum += 1;

                if i > 0 {
                    result += i * (1 << (i - 1));
                }
            }
        }

        result + sum
    }

    /// 计算小于等于x所有数的数位对幂的贡献之和
    fn count_power(x: i64) -> i64 {
        let mut result = 0;
        let mut sum = 0;

        for i in (0..=60).rev() {
            if (1 << i) & x != 0 {
                result += sum * (1 << i);
                sum += i;

                if i > 0 {
                    result += i * (i - 1) / 2 * (1 << (i - 1));
                }
            }
        }

        result + sum
    }

    /// Calculate (x ^ y) % mod_number
    fn power_mod(x: i64, y: i64, mod_number: i64) -> i64 {
        let mut result = 1i64;
        let (mut x, mut y) = (x, y);

        while y != 0 {
            if y & 1 == 1 {
                result = result * x % mod_number;
            }

            x = x * x % mod_number;
            y = y >> 1;
        }

        result
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_3145() {
        assert_eq!(
            vec![4],
            Solution::find_products_of_elements(vec![vec![1, 3, 7]])
        );
        assert_eq!(
            vec![2, 2],
            Solution::find_products_of_elements(vec![vec![2, 5, 3], vec![7, 7, 4]])
        );
    }
}

// Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3145: Find Products of Elements of Big Array
// 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;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(q × log M)

Space

O(log M)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.