LeetCode 3145 - Find Products of Elements of Big Array

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Bit Manipulation

Solution

Problem Understanding

The problem asks us to work with a conceptual infinite array called big_nums, which is generated by taking every positive integer i, converting it to its powerful array (the sorted array of powers of two that sum to i), and concatenating all these arrays sequentially. For instance, 1 → [1], 2 → [2], 3 → [1, 2], 4 → [4], 5 → [1, 4], and so on. The array grows indefinitely.

Given a series of queries in the form [fromi, toi, modi], the task is to compute the product of big_nums[fromi] to big_nums[toi] modulo modi. The input indices can be extremely large, up to 10^15, so we cannot generate the array explicitly. Instead, we must compute products efficiently using properties of powers of two, modular arithmetic, and the predictable structure of big_nums.

The constraints tell us a few important things: queries.length <= 500, but indices fromi and toi can be as large as 10^15. The modulo modi is relatively small (<= 10^5). This means any naive array construction will fail, and we must rely on mathematical reasoning rather than brute force. The problem guarantees that each number can be decomposed uniquely into powers of two, which is the foundation of the algorithm.

Important edge cases include queries that start or end at very high indices, queries of length 1, or queries where modi is 1, which would always yield 0.

Approaches

The brute-force approach would be to explicitly generate big_nums until we reach the largest toi in the queries, then compute the product for each query. While this is straightforward, it is infeasible due to memory and time constraints since big_nums grows extremely quickly.

The optimal approach uses the observation that each number is represented as a sum of powers of two. The number of times each power of two appears up to a certain index follows a predictable pattern, which can be efficiently computed using binary search and bit manipulation. Once we know the count of each power of two in a range, we can compute the product modulo modi without generating big_nums. Specifically, because the product is only powers of two, we can use exponentiation modulo modi to calculate the result quickly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(L) per query, L = length of range	O(L)	Explicitly generate `big_nums` and multiply, infeasible for large `toi`
Optimal	O(60 * log(toi)) per query	O(1)	Compute count of each power of two using bit decomposition and use modular exponentiation

Algorithm Walkthrough

Recognize that big_nums consists of powers of two derived from each integer i via its binary representation. Every 1 bit at position k in i contributes a 2^k to big_nums.
For a query [fromi, toi, modi], the goal is to compute the product of the powers of two in this range modulo modi.
Instead of constructing big_nums, define a helper function count_powers(u, power) that returns how many times 2^power appears in the first u elements of big_nums.
Use binary search over i to find how many numbers contribute to big_nums up to index u and sum the contributions of 2^power.
Once counts of all relevant powers of two in the range [fromi, toi] are known, calculate the product using modular exponentiation: product = 2^(sum of exponents) % modi.
Repeat for each query and return the results.

Why it works: The key invariant is that each integer’s powerful array is exactly its binary decomposition. Therefore, the frequency of each power of two is deterministic, and modular arithmetic allows combining these powers efficiently without overflow.

Python Solution

from typing import List

class Solution:
    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        def count_power(u: int, p: int) -> int:
            total, i = 0, 1
            while i <= u:
                block = 1 << (p + 1)
                total += ((u - i + 1) // block) * (1 << p)
                remainder = (u - i + 1) % block
                total += min(remainder, 1 << p)
                i += block
            return total

        def mod_pow2(exponent: int, mod: int) -> int:
            result, base = 1, 2
            while exponent:
                if exponent % 2:
                    result = (result * base) % mod
                base = (base * base) % mod
                exponent //= 2
            return result

        ans = []
        for l, r, m in queries:
            l += 1
            r += 1
            total = 0
            for p in range(60):
                c = count_power(r, p) - count_power(l - 1, p)
                if c:
                    total = (total + pow(2, p, m) * c) % m
            ans.append(total % m)
        return ans

Explanation: count_power(u, p) computes how many times 2^p appears in the first u elements. The mod_pow2 function efficiently computes 2^exponent % mod using binary exponentiation. For each query, we sum contributions from all powers of two, taking care to handle modular arithmetic throughout.

Go Solution

package main

func countPower(u int64, p int) int64 {
	var total, i int64 = 0, 1
	for i <= u {
		block := int64(1) << (p + 1)
		total += ((u - i + 1) / block) * (1 << p)
		remainder := (u - i + 1) % block
		if remainder > (1<<p) {
			total += int64(1 << p)
		} else {
			total += remainder
		}
		i += block
	}
	return total
}

func modPow2(exponent int64, mod int64) int64 {
	result, base := int64(1), int64(2)
	for exponent > 0 {
		if exponent%2 == 1 {
			result = (result * base) % mod
		}
		base = (base * base) % mod
		exponent /= 2
	}
	return result
}

func findProductsOfElements(queries [][]int64) []int {
	ans := make([]int, len(queries))
	for idx, q := range queries {
		l, r, m := q[0]+1, q[1]+1, q[2]
		var total int64 = 0
		for p := 0; p < 60; p++ {
			c := countPower(r, p) - countPower(l-1, p)
			if c > 0 {
				total = (total + modPow2(c, m)) % m
			}
		}
		ans[idx] = int(total % m)
	}
	return ans
}

Go-specific Notes: Go requires explicit int64 arithmetic for large numbers. Slices are used for query results, and modular exponentiation is implemented iteratively. Care is taken to avoid overflow with int64 types.

Worked Examples

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

big_nums[1..3] = [2, 1, 2]

product = 2 * 1 * 2 = 4

4 % 7 = 4 → answer [4]

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

big_nums[2..5] = [1,2,4,1] → product = 8 → 8 % 3 = 2

big_nums[7] = 2 → 2 % 4 = 2 → answer [2,2]

State of count_power would show how many times each power of two contributes in these ranges.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(Q * 60 * log(max_index))	Each query processes up to 60 powers of two, using O(log max_index) arithmetic per power
Space	O(1)	Only counters and temporary variables are needed

Because the algorithm never constructs big_nums explicitly, it is highly efficient even for very large indices.

Test Cases

# Provided examples
assert Solution().findProductsOfElements([[1,3,7]]) == [4] # single query
assert Solution().findProductsOfElements([[2,5,3],[7,7,4]]) == [2,2] # two queries

# Edge cases
assert Solution().findProductsOfElements([[0,0,1]]) == [0] # modulo 1
assert Solution().findProductsOfElements([[0,0,5]]) == [