Facebook Pixel

3145. Find Products of Elements of Big Array

HardBit ManipulationArrayBinary Search
Leetcode Link

Problem Description

Given the concept of a powerful array for a non-negative integer x, which is defined as the shortest sorted array of powers of two that sum up to x. For example:

  • The powerful array of 1 is [1] (binary: 0001)
  • The powerful array of 10 is [2, 8] (binary: 01010)
  • The powerful array of 13 is [1, 4, 8] (binary: 01101)

The powerful array essentially represents the powers of 2 corresponding to the 1-bits in the binary representation of the number.

A special array called big_nums is created by concatenating the powerful arrays of all positive integers in ascending order:

  • Powerful array of 1: [1]
  • Powerful array of 2: [2]
  • Powerful array of 3: [1, 2]
  • Powerful array of 4: [4]
  • Powerful array of 5: [1, 4]
  • And so on...

So big_nums = [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]

You are given a 2D integer matrix queries, where each query is of the form [from_i, to_i, mod_i]. For each query, you need to:

  1. Take the subarray from big_nums[from_i] to big_nums[to_i] (inclusive)
  2. Calculate the product of all elements in this subarray
  3. Return the result modulo mod_i

The task is to return an array answer where answer[i] contains the result for the i-th query.

Key Insight: Since all elements in big_nums are powers of 2, the product of elements like 2^a × 2^b × 2^c equals 2^(a+b+c). Therefore, the problem reduces to finding the sum of exponents in the specified range and then computing 2^sum % mod.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Since every element in big_nums is a power of 2, multiplying them together means adding their exponents. For example, 2 × 8 × 4 = 2^1 × 2^3 × 2^2 = 2^(1+3+2) = 2^6. This transforms our problem from finding products to finding sums of exponents.

The challenge is that big_nums can be extremely large (as we concatenate powerful arrays for all positive integers), so we can't build it explicitly. We need a way to directly calculate the sum of exponents for any range [left, right] without constructing the entire array.

The key observation is that there's a pattern in how powerful arrays are generated. Looking at the binary representations:

  • Numbers from [1, 1] have at most 1 bit set
  • Numbers from [2, 3] have at most 2 bits set
  • Numbers from [4, 7] have at most 3 bits set
  • Numbers from [8, 15] have at most 4 bits set

More generally, numbers in the range [2^i, 2^(i+1) - 1] share similar bit patterns. The powerful arrays for these numbers follow a recursive structure - they're similar to the powerful arrays of numbers in [0, 2^i - 1], but with an additional 2^i term.

This pattern allows us to precompute:

  • cnt[i]: the total count of elements in powerful arrays for all numbers from 0 to 2^i - 1
  • s[i]: the sum of all exponents in these powerful arrays

For any arbitrary position in big_nums, we can use binary search to find which number's powerful array it belongs to. Once we know the number, we can decompose it bit by bit to find the exact exponent at that position.

The solution uses a helper function f(i) to calculate the sum of exponents from position 0 to position i-1 in big_nums. Then for each query [left, right, mod], the answer is 2^(f(right + 1) - f(left)) % mod, which we compute using fast exponentiation.

Learn more about Binary Search patterns.

Solution Implementation

1from typing import List
2
3
4# Precompute values for optimization
5MAX_BITS = 50
6bit_count = [0] * (MAX_BITS + 1)  # Count of bits up to position i
7bit_sum = [0] * (MAX_BITS + 1)    # Sum of bit positions up to position i
8power_of_two = 1
9
10# Precompute cumulative bit counts and sums for powers of 2
11for i in range(1, MAX_BITS + 1):
12    bit_count[i] = bit_count[i - 1] * 2 + power_of_two
13    bit_sum[i] = bit_sum[i - 1] * 2 + power_of_two * (i - 1)
14    power_of_two *= 2
15
16
17def calculate_bit_index_and_sum(n: int) -> tuple:
18    """
19    Calculate the total number of bits and sum of bit positions
20    for all numbers from 1 to n in their binary representation.
21
22    Args:
23        n: Upper bound of the range
24
25    Returns:
26        Tuple of (total_bit_count, sum_of_bit_positions)
27    """
28    total_count = 0
29    total_sum = 0
30
31    while n > 0:
32        # Find the position of the most significant bit
33        msb_position = n.bit_length() - 1
34
35        # Add precomputed values for complete powers of 2
36        total_count += bit_count[msb_position]
37        total_sum += bit_sum[msb_position]
38
39        # Remove the highest power of 2
40        n -= 1 << msb_position
41
42        # Add contribution from remaining numbers
43        total_sum += (n + 1) * msb_position
44        total_count += n + 1
45
46    return (total_count, total_sum)
47
48
49def find_bit_position_sum(index: int) -> int:
50    """
51    Find the sum of bit positions up to the given index in the
52    sequence of all set bits from binary representations.
53
54    Args:
55        index: The target index in the bit sequence
56
57    Returns:
58        Sum of bit positions up to the index
59    """
60    # Binary search using the standard template
61    # Find first number where cumulative count >= index
62    left, right = 0, 1 << MAX_BITS
63    first_true_index = -1
64
65    while left <= right:
66        mid = (left + right) // 2
67        current_index, _ = calculate_bit_index_and_sum(mid)
68
69        if current_index >= index:  # feasible: count reaches target
70            first_true_index = mid
71            right = mid - 1
72        else:
73            left = mid + 1
74
75    # We want the largest number whose count is still < index
76    # That's one position before first_true_index
77    target = first_true_index - 1 if first_true_index != -1 else (1 << MAX_BITS)
78
79    # Calculate sum up to the found number
80    bit_index, position_sum = calculate_bit_index_and_sum(target)
81
82    # Calculate remaining bits needed
83    remaining_bits = index - bit_index
84    current_number = target + 1
85
86    # Add bit positions for remaining bits using lowbit technique
87    for _ in range(remaining_bits):
88        # Get the rightmost set bit (lowbit)
89        lowest_bit = current_number & -current_number
90        # Add the position of this bit (0-indexed)
91        position_sum += lowest_bit.bit_length() - 1
92        # Remove the rightmost set bit
93        current_number -= lowest_bit
94
95    return position_sum
96
97
98class Solution:
99    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
100        """
101        Find products of elements in given ranges where elements are powers of 2
102        based on bit positions in the binary representation sequence.
103
104        Args:
105            queries: List of [left, right, mod] queries
106
107        Returns:
108            List of results where each result is 2^(sum of bit positions) % mod
109        """
110        results = []
111
112        for left, right, mod in queries:
113            # Calculate sum of bit positions in range [left, right]
114            # Note: Using 1-indexed positions, so add 1 to right
115            sum_of_positions = find_bit_position_sum(right + 1) - find_bit_position_sum(left)
116
117            # Result is 2^sum_of_positions % mod
118            result = pow(2, sum_of_positions, mod)
119            results.append(result)
120
121        return results
122
1class Solution {
2    // Maximum number of bits to consider
3    private static final int MAX_BITS = 50;
4
5    // Precomputed arrays for optimization
6    // count[i]: number of set bits in all numbers from 0 to 2^i - 1
7    // sum[i]: sum of positions of set bits in all numbers from 0 to 2^i - 1
8    private static final long[] count = new long[MAX_BITS + 1];
9    private static final long[] sum = new long[MAX_BITS + 1];
10
11    // Static initialization block to precompute values
12    static {
13        long powerOfTwo = 1;
14        for (int i = 1; i <= MAX_BITS; i++) {
15            // Each bit position appears in half of the numbers in range [0, 2^i)
16            count[i] = count[i - 1] * 2 + powerOfTwo;
17            // Sum includes previous sum doubled plus contribution of new bit
18            sum[i] = sum[i - 1] * 2 + powerOfTwo * (i - 1);
19            powerOfTwo *= 2;
20        }
21    }
22
23    /**
24     * Calculate the number of set bits and their position sum for all numbers from 0 to x
25     * @param x The upper bound (inclusive)
26     * @return Array containing [total count of set bits, sum of their positions]
27     */
28    private static long[] numIdxAndSum(long x) {
29        long totalCount = 0;
30        long totalSum = 0;
31
32        while (x > 0) {
33            // Find the position of the highest set bit
34            int bitPosition = Long.SIZE - Long.numberOfLeadingZeros(x) - 1;
35
36            // Add precomputed values for complete range [0, 2^bitPosition)
37            totalCount += count[bitPosition];
38            totalSum += sum[bitPosition];
39
40            // Remove the highest bit value from x
41            x -= 1L << bitPosition;
42
43            // Add contribution of the highest bit in remaining numbers
44            totalSum += (x + 1) * bitPosition;
45            totalCount += x + 1;
46        }
47
48        return new long[] {totalCount, totalSum};
49    }
50
51    /**
52     * Find the sum of positions for the first i set bits in the infinite bit sequence
53     * @param i The number of set bits to consider
54     * @return Sum of positions of the first i set bits
55     */
56    private static long f(long i) {
57        // Binary search using the standard template
58        // Find first number where cumulative count >= i
59        long left = 0;
60        long right = 1L << MAX_BITS;
61        long firstTrueIndex = -1;
62
63        while (left <= right) {
64            long mid = left + (right - left) / 2;
65            long[] result = numIdxAndSum(mid);
66            long bitCount = result[0];
67
68            if (bitCount >= i) {  // feasible: count reaches target
69                firstTrueIndex = mid;
70                right = mid - 1;
71            } else {
72                left = mid + 1;
73            }
74        }
75
76        // We want the largest number whose count is still < i
77        // That's one position before firstTrueIndex
78        long target = firstTrueIndex != -1 ? firstTrueIndex - 1 : (1L << MAX_BITS);
79
80        // Get the total sum up to number 'target'
81        long[] result = numIdxAndSum(target);
82        long totalSum = result[1];
83        long bitCount = result[0];
84
85        // Calculate remaining bits needed
86        i -= bitCount;
87
88        // Process the next number (target + 1) bit by bit
89        long currentNumber = target + 1;
90        for (int j = 0; j < i; j++) {
91            // Find the lowest set bit using bit manipulation
92            long lowestBit = currentNumber & -currentNumber;
93            // Add the position of this bit to the sum
94            totalSum += Long.numberOfTrailingZeros(lowestBit);
95            // Remove the lowest set bit
96            currentNumber -= lowestBit;
97        }
98
99        return totalSum;
100    }
101
102    /**
103     * Main solution method to find products of elements based on queries
104     * @param queries Array of queries, each containing [left, right, mod]
105     * @return Array of results for each query
106     */
107    public int[] findProductsOfElements(long[][] queries) {
108        int numberOfQueries = queries.length;
109        int[] results = new int[numberOfQueries];
110
111        for (int i = 0; i < numberOfQueries; i++) {
112            long leftBound = queries[i][0];
113            long rightBound = queries[i][1];
114            long modValue = queries[i][2];
115
116            // Calculate the total power of 2 needed
117            long totalPower = f(rightBound + 1) - f(leftBound);
118
119            // Calculate 2^totalPower mod modValue using fast exponentiation
120            results[i] = qpow(2, totalPower, modValue);
121        }
122
123        return results;
124    }
125
126    /**
127     * Fast modular exponentiation: calculates (base^exponent) % modulus
128     * @param base The base number
129     * @param exponent The exponent
130     * @param modulus The modulus value
131     * @return (base^exponent) % modulus
132     */
133    private int qpow(long base, long exponent, long modulus) {
134        long result = 1 % modulus;
135
136        // Binary exponentiation algorithm
137        while (exponent > 0) {
138            // If current bit is set, multiply result by current base
139            if ((exponent & 1) == 1) {
140                result = result * base % modulus;
141            }
142            // Square the base for next bit position
143            base = base * base % modulus;
144            // Move to next bit
145            exponent >>= 1;
146        }
147
148        return (int) result;
149    }
150}
151
1using ll = long long;
2
3// Maximum bit position to consider
4const int MAX_BITS = 50;
5
6// Precomputed arrays for optimization
7ll count_up_to_power[MAX_BITS + 1];  // Count of elements up to 2^i - 1
8ll sum_up_to_power[MAX_BITS + 1];    // Sum of bit positions up to 2^i - 1
9ll power_of_two = 1;
10
11// Initialize precomputed arrays at program startup
12auto initialize = [] {
13    count_up_to_power[0] = 0;
14    sum_up_to_power[0] = 0;
15
16    // For each power of 2, precompute count and sum of bit positions
17    for (int i = 1; i <= MAX_BITS; ++i) {
18        // Each level doubles the previous count plus adds 2^(i-1) new elements
19        count_up_to_power[i] = count_up_to_power[i - 1] * 2 + power_of_two;
20
21        // Each level doubles the previous sum plus adds contribution from new elements
22        sum_up_to_power[i] = sum_up_to_power[i - 1] * 2 + power_of_two * (i - 1);
23
24        power_of_two *= 2;
25    }
26    return 0;
27}();
28
29// Calculate the number of elements and sum of bit positions up to value x
30pair<ll, ll> calculateCountAndSum(ll x) {
31    ll element_count = 0;
32    ll bit_position_sum = 0;
33
34    while (x > 0) {
35        // Find the highest set bit position in x
36        int highest_bit = 63 - __builtin_clzll(x);
37
38        // Add precomputed values for all numbers less than 2^highest_bit
39        element_count += count_up_to_power[highest_bit];
40        bit_position_sum += sum_up_to_power[highest_bit];
41
42        // Remove the highest bit from x
43        x -= 1LL << highest_bit;
44
45        // Add contribution from remaining numbers (x+1 numbers, each contributing highest_bit)
46        bit_position_sum += (x + 1) * highest_bit;
47        element_count += x + 1;
48    }
49
50    return make_pair(element_count, bit_position_sum);
51}
52
53// Find the sum of bit positions from index 1 to index i (1-indexed)
54ll calculateSumUpToIndex(ll i) {
55    // Binary search using the standard template
56    // Find first number where cumulative count >= i
57    ll left = 0;
58    ll right = 1LL << MAX_BITS;
59    ll firstTrueIndex = -1;
60
61    while (left <= right) {
62        ll mid = left + (right - left) / 2;
63        auto [count, sum] = calculateCountAndSum(mid);
64
65        if (count >= i) {  // feasible: count reaches target
66            firstTrueIndex = mid;
67            right = mid - 1;
68        } else {
69            left = mid + 1;
70        }
71    }
72
73    // We want the largest number whose count is still < i
74    // That's one position before firstTrueIndex
75    ll target = firstTrueIndex != -1 ? firstTrueIndex - 1 : (1LL << MAX_BITS);
76
77    // Get the sum up to the found value
78    auto [total_count, total_sum] = calculateCountAndSum(target);
79
80    // Calculate remaining elements needed
81    i -= total_count;
82
83    // Process remaining elements one by one
84    ll current_value = target + 1;
85    for (int j = 0; j < i; ++j) {
86        // Find the lowest set bit (position of rightmost 1)
87        ll lowest_bit_mask = current_value & -current_value;
88
89        // Add the position of the lowest set bit to the sum
90        total_sum += __builtin_ctzll(lowest_bit_mask);
91
92        // Remove the lowest set bit from current value
93        current_value -= lowest_bit_mask;
94    }
95
96    return total_sum;
97}
98
99// Fast modular exponentiation: compute (base^exponent) % modulo
100ll modularPower(ll base, ll exponent, ll modulo) {
101    ll result = 1 % modulo;
102    base = base % modulo;
103
104    while (exponent > 0) {
105        // If exponent is odd, multiply result by base
106        if (exponent & 1) {
107            result = result * base % modulo;
108        }
109        // Square the base and halve the exponent
110        base = base * base % modulo;
111        exponent >>= 1;
112    }
113
114    return result;
115}
116
117class Solution {
118public:
119    // Find products of elements for given query ranges
120    // Each query contains [left_index, right_index, modulo]
121    vector<int> findProductsOfElements(vector<vector<ll>>& queries) {
122        int query_count = queries.size();
123        vector<int> results(query_count);
124
125        // Process each query
126        for (int i = 0; i < query_count; ++i) {
127            ll left_index = queries[i][0];
128            ll right_index = queries[i][1];
129            ll modulo = queries[i][2];
130
131            // Calculate the sum of bit positions in the range [left, right]
132            // This sum will be the exponent for 2^sum
133            ll exponent_sum = calculateSumUpToIndex(right_index + 1) - calculateSumUpToIndex(left_index);
134
135            // The product is 2^exponent_sum mod modulo
136            results[i] = static_cast<int>(modularPower(2, exponent_sum, modulo));
137        }
138
139        return results;
140    }
141};
142
1type ll = bigint;
2
3// Maximum bit position to consider
4const MAX_BITS = 50;
5
6// Precomputed arrays for optimization
7const countUpToPower: ll[] = new Array(MAX_BITS + 1);  // Count of elements up to 2^i - 1
8const sumUpToPower: ll[] = new Array(MAX_BITS + 1);    // Sum of bit positions up to 2^i - 1
9
10// Initialize precomputed arrays at program startup
11function initialize(): void {
12    countUpToPower[0] = 0n;
13    sumUpToPower[0] = 0n;
14    let powerOfTwo = 1n;
15
16    // For each power of 2, precompute count and sum of bit positions
17    for (let i = 1; i <= MAX_BITS; i++) {
18        // Each level doubles the previous count plus adds 2^(i-1) new elements
19        countUpToPower[i] = countUpToPower[i - 1] * 2n + powerOfTwo;
20
21        // Each level doubles the previous sum plus adds contribution from new elements
22        sumUpToPower[i] = sumUpToPower[i - 1] * 2n + powerOfTwo * BigInt(i - 1);
23
24        powerOfTwo *= 2n;
25    }
26}
27
28// Call initialization
29initialize();
30
31// Helper function to find the position of the highest set bit
32function getHighestBitPosition(x: ll): number {
33    if (x === 0n) return -1;
34    let position = 0;
35    let temp = x;
36    while (temp > 0n) {
37        position++;
38        temp >>= 1n;
39    }
40    return position - 1;
41}
42
43// Helper function to find the position of the lowest set bit
44function getLowestBitPosition(x: ll): number {
45    if (x === 0n) return -1;
46    let position = 0;
47    let temp = x;
48    while ((temp & 1n) === 0n) {
49        position++;
50        temp >>= 1n;
51    }
52    return position;
53}
54
55// Calculate the number of elements and sum of bit positions up to value x
56function calculateCountAndSum(x: ll): [ll, ll] {
57    let elementCount = 0n;
58    let bitPositionSum = 0n;
59
60    while (x > 0n) {
61        // Find the highest set bit position in x
62        const highestBit = getHighestBitPosition(x);
63
64        // Add precomputed values for all numbers less than 2^highestBit
65        elementCount += countUpToPower[highestBit];
66        bitPositionSum += sumUpToPower[highestBit];
67
68        // Remove the highest bit from x
69        x -= 1n << BigInt(highestBit);
70
71        // Add contribution from remaining numbers (x+1 numbers, each contributing highestBit)
72        bitPositionSum += (x + 1n) * BigInt(highestBit);
73        elementCount += x + 1n;
74    }
75
76    return [elementCount, bitPositionSum];
77}
78
79// Find the sum of bit positions from index 1 to index i (1-indexed)
80function calculateSumUpToIndex(i: ll): ll {
81    // Binary search using the standard template
82    // Find first number where cumulative count >= i
83    let left = 0n;
84    let right = 1n << BigInt(MAX_BITS);
85    let firstTrueIndex = -1n;
86
87    while (left <= right) {
88        const mid = (left + right) / 2n;
89        const [count, sum] = calculateCountAndSum(mid);
90
91        if (count >= i) {  // feasible: count reaches target
92            firstTrueIndex = mid;
93            right = mid - 1n;
94        } else {
95            left = mid + 1n;
96        }
97    }
98
99    // We want the largest number whose count is still < i
100    // That's one position before firstTrueIndex
101    const target = firstTrueIndex !== -1n ? firstTrueIndex - 1n : (1n << BigInt(MAX_BITS));
102
103    // Get the sum up to the found value
104    const [totalCount, totalSum] = calculateCountAndSum(target);
105
106    // Calculate remaining elements needed
107    i -= totalCount;
108
109    // Process remaining elements one by one
110    let currentValue = target + 1n;
111    let resultSum = totalSum;
112
113    for (let j = 0n; j < i; j++) {
114        // Find the lowest set bit (position of rightmost 1)
115        const lowestBitMask = currentValue & -currentValue;
116
117        // Add the position of the lowest set bit to the sum
118        resultSum += BigInt(getLowestBitPosition(lowestBitMask));
119
120        // Remove the lowest set bit from current value
121        currentValue -= lowestBitMask;
122    }
123
124    return resultSum;
125}
126
127// Fast modular exponentiation: compute (base^exponent) % modulo
128function modularPower(base: ll, exponent: ll, modulo: ll): ll {
129    let result = 1n % modulo;
130    base = base % modulo;
131
132    while (exponent > 0n) {
133        // If exponent is odd, multiply result by base
134        if ((exponent & 1n) === 1n) {
135            result = (result * base) % modulo;
136        }
137        // Square the base and halve the exponent
138        base = (base * base) % modulo;
139        exponent >>= 1n;
140    }
141
142    return result;
143}
144
145// Find products of elements for given query ranges
146// Each query contains [leftIndex, rightIndex, modulo]
147function findProductsOfElements(queries: number[][]): number[] {
148    const queryCount = queries.length;
149    const results: number[] = new Array(queryCount);
150
151    // Process each query
152    for (let i = 0; i < queryCount; i++) {
153        const leftIndex = BigInt(queries[i][0]);
154        const rightIndex = BigInt(queries[i][1]);
155        const modulo = BigInt(queries[i][2]);
156
157        // Calculate the sum of bit positions in the range [left, right]
158        // This sum will be the exponent for 2^sum
159        const exponentSum = calculateSumUpToIndex(rightIndex + 1n) - calculateSumUpToIndex(leftIndex);
160
161        // The product is 2^exponentSum mod modulo
162        results[i] = Number(modularPower(2n, exponentSum, modulo));
163    }
164
165    return results;
166}
167

Solution Approach

The solution consists of three main components: precomputation, binary search with bit manipulation, and query processing.

1. Precomputation of Pattern Tables

First, we precompute two arrays cnt and s for the first m=50 groups (sufficient since 2^50 covers the problem constraints):

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
  • cnt[i]: Total number of elements in powerful arrays for numbers [0, 2^i - 1]
  • s[i]: Sum of all exponents in these powerful arrays
  • The recurrence relations come from the fact that numbers in [2^i, 2^(i+1) - 1] have patterns similar to [0, 2^i - 1] but with an added 2^i term

2. Computing Index and Sum for Any Number

The function num_idx_and_sum(x) calculates the total number of elements and sum of exponents for all powerful arrays up to number x:

def num_idx_and_sum(x: int) -> tuple:
    idx = 0
    total_sum = 0
    while x:
        i = x.bit_length() - 1  # Find highest set bit
        idx += cnt[i]
        total_sum += s[i]
        x -= 1 << i  # Remove the highest bit
        total_sum += (x + 1) * i  # Add contribution of remaining numbers
        idx += x + 1
    return (idx, total_sum)

This works by processing x bit by bit from the highest bit. For example, if x = 13 = 2^3 + 2^2 + 2^0:

  • First, handle numbers [0, 2^3 - 1] using precomputed values
  • Then handle remaining numbers [2^3, 13], which is like handling [0, 5] with each exponent increased by 3
  • Recursively process until x becomes 0

3. Finding Prefix Sum at Position i

The function f(i) finds the sum of exponents from position 0 to position i-1 in big_nums. We use binary search to find the largest number whose powerful array ends before position i.

The feasible condition is: "Does the count of elements up to number mid reach at least i?" We want the last position where this is FALSE (count < i), so we search for the first TRUE and take one position before.

def f(i: int) -> int:
    left, right = 0, 1 << m
    first_true_index = -1

    while left <= right:
        mid = (left + right) // 2
        idx, _ = num_idx_and_sum(mid)
        if idx >= i:  # feasible: count reaches target
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    # The answer is one position before first_true_index
    target = first_true_index - 1 if first_true_index != -1 else (1 << m)

    idx, total_sum = num_idx_and_sum(target)
    i -= idx
    x = target + 1
    for _ in range(i):
        y = x & -x  # Extract lowest set bit
        total_sum += y.bit_length() - 1
        x -= y
    return total_sum

This uses the standard binary search template to find the first number where the cumulative count reaches i. Then we take the number just before it (since we want the largest number whose powerful array ends before position i) and calculate the remaining elements using bit manipulation (x & -x extracts the lowest set bit).

4. Processing Queries

Finally, for each query [left, right, mod]:

def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
    return [pow(2, f(right + 1) - f(left), mod) for left, right, mod in queries]

The answer is 2^(f(right + 1) - f(left)) % mod, computed using Python's built-in pow function with three arguments for efficient modular exponentiation.

The time complexity is O(q * log^2(n)) where q is the number of queries and n is the range of indices, due to the binary search and bit operations.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have a query [7, 11, 13], meaning we want to find the product of elements from index 7 to 11 in big_nums, then take the result modulo 13.

Step 1: Understanding big_nums

First, let's build a portion of big_nums by finding powerful arrays for the first few numbers:

  • 1 (binary: 0001) → powerful array: [1]
  • 2 (binary: 0010) → powerful array: [2]
  • 3 (binary: 0011) → powerful array: [1, 2]
  • 4 (binary: 0100) → powerful array: [4]
  • 5 (binary: 0101) → powerful array: [1, 4]
  • 6 (binary: 0110) → powerful array: [2, 4]
  • 7 (binary: 0111) → powerful array: [1, 2, 4]

So big_nums = [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, ...]

  • Indices: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]

Step 2: Extract the subarray

For our query [7, 11, 13], we need elements at indices 7-11:

  • big_nums[7:12] = [2, 4, 1, 2, 4]

Step 3: Convert to exponents

Since these are all powers of 2:

  • 2 = 2^1, 4 = 2^2, 1 = 2^0, 2 = 2^1, 4 = 2^2
  • Exponents: [1, 2, 0, 1, 2]

Step 4: Calculate sum of exponents

Using the f() function:

  • f(12) calculates sum of exponents from index 0 to 11
  • f(7) calculates sum of exponents from index 0 to 6

Let's trace through f(7):

  1. Binary search finds that powerful arrays for numbers 1-5 contribute exactly 7 elements
  2. So position 7 is at the start of number 6's powerful array
  3. f(7) returns sum of exponents for indices 0-6, which equals:
    • Number 1: exponent 0 (for element 1)
    • Number 2: exponent 1 (for element 2)
    • Number 3: exponents 0, 1 (for elements 1, 2)
    • Number 4: exponent 2 (for element 4)
    • Number 5: exponents 0, 2 (for elements 1, 4)
    • Total: 0 + 1 + (0+1) + 2 + (0+2) = 6

Similarly, f(12) would calculate the sum including indices 7-11:

  • Additional exponents from indices 7-11: 1, 2, 0, 1, 2
  • f(12) = f(7) + (1+2+0+1+2) = 6 + 6 = 12

Step 5: Compute the result

The sum of exponents in range [7, 11] is:

  • f(12) - f(7) = 12 - 6 = 6

Therefore, the product is:

  • 2^6 = 64

And the final answer:

  • 64 % 13 = 12

The beauty of this approach is that we never actually build big_nums. Instead, we use the pattern in binary representations to directly compute the sum of exponents for any range, making it efficient even for very large indices.

Time and Space Complexity

Time Complexity: O(q × log M)

The main time complexity comes from the findProductsOfElements method which processes q queries. For each query, it calls function f twice (for right + 1 and left).

Inside function f:

  • The binary search loop runs O(log M) iterations, where M is the upper bound (1 << m which represents 2^50)
  • Within each binary search iteration, num_idx_and_sum is called, which has a while loop that runs at most O(log M) times (based on the bit length of x)
  • After the binary search, there's another loop that runs i times in the worst case, but since we're working with bit operations on numbers up to M, this is also bounded by O(log M)

Therefore, for each query: O(log M × log M) which simplifies to O(log² M) for the binary search portion, but the dominant operation is actually O(log M) due to the nature of the bit manipulation operations.

Overall: O(q × log M) where q is the number of queries and M ≤ 10^15 in this problem.

Space Complexity: O(log M)

The space complexity is determined by:

  • The precomputed arrays cnt and s, each of size m + 1 where m = 50, which is O(log M) since m = log₂(M)
  • The recursive depth and local variables in functions are O(1)
  • No additional data structures that scale with input size are used

Therefore, the space complexity is O(log M).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using different binary search variants that don't match the standard template can lead to off-by-one errors and incorrect results:

# WRONG: Non-standard variant
while left < right:
    mid = (left + right + 1) >> 1
    if count < index:
        left = mid
    else:
        right = mid - 1
return left  # Returns result directly without tracking

The Solution: Use the standard template that tracks first_true_index:

# CORRECT: Standard template
left, right = 0, max_value
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # count >= index
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

# Handle result based on first_true_index
target = first_true_index - 1 if first_true_index != -1 else max_value

2. Off-by-One Errors in Index Calculation

The most common pitfall in this problem is mishandling the 0-indexed vs 1-indexed conversion when calculating bit positions and array indices.

The Pitfall:

  • The problem uses 0-indexed arrays for queries (big_nums[from_i] to big_nums[to_i])
  • The internal logic often works with 1-indexed counting for numbers (1, 2, 3, ...)
  • Mixing these can lead to incorrect range calculations

Example of the Error:

# WRONG: Forgetting to adjust for 0-indexing
def findProductsOfElements(self, queries):
    return [pow(2, f(right) - f(left), mod) for left, right, mod in queries]
    # This misses the last element in the range!

The Solution:

# CORRECT: Properly handle inclusive range [left, right]
def findProductsOfElements(self, queries):
    return [pow(2, f(right + 1) - f(left), mod) for left, right, mod in queries]
    # f(right + 1) gives sum up to and including index right

3. Integer Overflow in Intermediate Calculations

The Pitfall: When calculating total_sum += (n + 1) * msb_position, the multiplication can overflow for large values even though Python handles big integers well. The real issue is when using this pattern in other languages or when optimizing with fixed-size integers.

The Solution: Always use appropriate data types and be mindful of the order of operations:

# Better practice - accumulate incrementally if needed
total_sum += (n + 1) * msb_position  # Python handles this, but be careful in C++/Java

4. Incorrect Lowbit Extraction Logic

The Pitfall: The lowbit operation x & -x extracts the rightmost set bit, but developers often misunderstand what this returns:

# WRONG: Thinking lowbit gives the bit position directly
bit_position = x & -x  # This gives 2^position, not position!

# WRONG: Off-by-one in bit position calculation
position = (x & -x).bit_length()  # This is 1-indexed, not 0-indexed

The Solution:

# CORRECT: Get the actual bit position (0-indexed)
lowest_bit = current_number & -current_number
position = lowest_bit.bit_length() - 1  # Subtract 1 for 0-indexing

5. Modular Arithmetic Errors

The Pitfall: Computing large powers before taking modulo:

# WRONG: Will cause overflow or be extremely slow
result = (2 ** sum_of_positions) % mod

The Solution:

# CORRECT: Use built-in modular exponentiation
result = pow(2, sum_of_positions, mod)

6. Precomputation Array Size

The Pitfall: Using insufficient precomputation size:

# WRONG: May not cover all test cases
MAX_BITS = 30  # Too small for large indices

The Solution:

# CORRECT: Use sufficient size based on constraints
MAX_BITS = 50  # Covers up to 2^50 which is more than enough

Key Debugging Tips:

  1. Test with small examples where you can manually verify the big_nums array
  2. Print intermediate values in calculate_bit_index_and_sum to verify correctness
  3. Verify that f(i) returns the correct cumulative sum for known positions
  4. Test edge cases: queries with left=0, right=0, and single-element ranges
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More