#3145

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Products of Elements of Big Array

Solve queries on a massive array of powers of two using binary search to efficiently compute modular products of subarrays.

array binary search bit manipulation

Problem Statement

Given a conceptual array big_nums formed by concatenating the powerful arrays of all positive integers in ascending order, compute modular products efficiently. A powerful array of x is the sorted list of powers of two that sum to x, and it is unique for each x.

You are provided a 2D integer matrix queries, where each query queries[i] = [fromi, toi, modi] requires calculating the product (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) modulo modi. The array length is extremely large, so naive iteration over big_nums is impractical.

Examples

Example 1

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

Output: [4]

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]

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

Solution Approach

Binary Search on Valid Answer Space

Use binary search to determine how many numbers contribute to each power of two up to the given index. This allows computing the count of each element in big_nums without explicitly generating the entire array.

Bitwise Counting per Position

For each bit position, calculate f(n, i) as the total number of numbers from 1 to n with the i-th bit set. This reduces computation to O(log n) per bit and avoids full array traversal.

Modular Product Calculation

Combine the counts from binary search with modular arithmetic. Compute the modular product for each query using repeated squaring to handle extremely large subarray sizes efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of queries and the bit-length of numbers, typically O(queries * log(max_index) * log(max_bit)), while space complexity is O(log(max_index) * log(max_bit)) for precomputed counts.

What Interviewers Usually Probe

Look for an approach that avoids building the entire big_nums array explicitly.
Check if the candidate can compute bit contributions using O(log n) methods.
Verify understanding of modular arithmetic on large products.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate big_nums entirely leads to memory overflow.
Failing to compute bit contributions correctly for large indices.
Ignoring modular reduction during intermediate multiplication causes overflow.

Follow-up variants

Compute sums instead of products for big_nums subarrays using the same binary search strategy.
Handle queries where elements are filtered by additional conditions on powers of two.
Apply the same binary search over valid answer space for ranges in 2D matrices built from powerful arrays.

FAQ

What is a powerful array and why is it unique?

A powerful array of x is the shortest sorted array of powers of two that sum to x. Its uniqueness comes from the binary representation of x, ensuring no two arrays produce the same sum.

How does binary search help in Find Products of Elements of Big Array?

Binary search lets you count occurrences of each power of two up to a certain index efficiently, avoiding explicit construction of big_nums.

Can I generate the entire big_nums array for calculation?

No, generating big_nums is impractical due to its enormous size. Use binary search and bit counting instead.

How are modular products handled for very large ranges?

Use repeated squaring and modular arithmetic while combining counts of powers of two to compute products without overflow.

What common mistakes occur when solving this problem?

Typical mistakes include iterating through the full big_nums array, incorrect bit counting, and not applying modulo during intermediate multiplication steps.

terminal

Solution

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.

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]

Continue Practicing

#3171 find subarray with bitwise or closest to k #3117 minimum sum of values by dividing array #3116 kth smallest amount with single denomination combination