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 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:

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
  
    idx, total_sum = num_idx_and_sum(l)
    i -= idx
    x = l + 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 binary search to find the largest number whose powerful array ends before position i. Then it calculates the remaining elements from the next number's powerful array 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.

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 to find the number containing the index-th bit
61    left, right = 0, 1 << MAX_BITS
62  
63    while left < right:
64        mid = (left + right + 1) >> 1
65        current_index, _ = calculate_bit_index_and_sum(mid)
66      
67        if current_index < index:
68            left = mid
69        else:
70            right = mid - 1
71  
72    # Calculate sum up to the found number
73    bit_index, position_sum = calculate_bit_index_and_sum(left)
74  
75    # Calculate remaining bits needed
76    remaining_bits = index - bit_index
77    current_number = left + 1
78  
79    # Add bit positions for remaining bits using lowbit technique
80    for _ in range(remaining_bits):
81        # Get the rightmost set bit (lowbit)
82        lowest_bit = current_number & -current_number
83        # Add the position of this bit (0-indexed)
84        position_sum += lowest_bit.bit_length() - 1
85        # Remove the rightmost set bit
86        current_number -= lowest_bit
87  
88    return position_sum
89
90
91class Solution:
92    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
93        """
94        Find products of elements in given ranges where elements are powers of 2
95        based on bit positions in the binary representation sequence.
96      
97        Args:
98            queries: List of [left, right, mod] queries
99      
100        Returns:
101            List of results where each result is 2^(sum of bit positions) % mod
102        """
103        results = []
104      
105        for left, right, mod in queries:
106            # Calculate sum of bit positions in range [left, right]
107            # Note: Using 1-indexed positions, so add 1 to right
108            sum_of_positions = find_bit_position_sum(right + 1) - find_bit_position_sum(left)
109          
110            # Result is 2^sum_of_positions % mod
111            result = pow(2, sum_of_positions, mod)
112            results.append(result)
113      
114        return results
115
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 to find the number whose bits contribute to position i
58        long left = 0;
59        long right = 1L << MAX_BITS;
60      
61        while (left < right) {
62            long mid = (left + right + 1) >> 1;
63            long[] result = numIdxAndSum(mid);
64            long bitCount = result[0];
65          
66            if (bitCount < i) {
67                left = mid;
68            } else {
69                right = mid - 1;
70            }
71        }
72      
73        // Get the total sum up to number 'left'
74        long[] result = numIdxAndSum(left);
75        long totalSum = result[1];
76        long bitCount = result[0];
77      
78        // Calculate remaining bits needed
79        i -= bitCount;
80      
81        // Process the next number (left + 1) bit by bit
82        long currentNumber = left + 1;
83        for (int j = 0; j < i; j++) {
84            // Find the lowest set bit using bit manipulation
85            long lowestBit = currentNumber & -currentNumber;
86            // Add the position of this bit to the sum
87            totalSum += Long.numberOfTrailingZeros(lowestBit);
88            // Remove the lowest set bit
89            currentNumber -= lowestBit;
90        }
91      
92        return totalSum;
93    }
94
95    /**
96     * Main solution method to find products of elements based on queries
97     * @param queries Array of queries, each containing [left, right, mod]
98     * @return Array of results for each query
99     */
100    public int[] findProductsOfElements(long[][] queries) {
101        int numberOfQueries = queries.length;
102        int[] results = new int[numberOfQueries];
103      
104        for (int i = 0; i < numberOfQueries; i++) {
105            long leftBound = queries[i][0];
106            long rightBound = queries[i][1];
107            long modValue = queries[i][2];
108          
109            // Calculate the total power of 2 needed
110            long totalPower = f(rightBound + 1) - f(leftBound);
111          
112            // Calculate 2^totalPower mod modValue using fast exponentiation
113            results[i] = qpow(2, totalPower, modValue);
114        }
115      
116        return results;
117    }
118
119    /**
120     * Fast modular exponentiation: calculates (base^exponent) % modulus
121     * @param base The base number
122     * @param exponent The exponent
123     * @param modulus The modulus value
124     * @return (base^exponent) % modulus
125     */
126    private int qpow(long base, long exponent, long modulus) {
127        long result = 1 % modulus;
128      
129        // Binary exponentiation algorithm
130        while (exponent > 0) {
131            // If current bit is set, multiply result by current base
132            if ((exponent & 1) == 1) {
133                result = result * base % modulus;
134            }
135            // Square the base for next bit position
136            base = base * base % modulus;
137            // Move to next bit
138            exponent >>= 1;
139        }
140      
141        return (int) result;
142    }
143}
144
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 to find the largest value x such that 
56    // the count of elements up to x is less than i
57    ll left = 0;
58    ll right = 1LL << MAX_BITS;
59  
60    while (left < right) {
61        ll mid = (left + right + 1) >> 1;
62        auto [count, sum] = calculateCountAndSum(mid);
63      
64        if (count < i) {
65            left = mid;
66        } else {
67            right = mid - 1;
68        }
69    }
70  
71    // Get the sum up to the found value
72    auto [total_count, total_sum] = calculateCountAndSum(left);
73  
74    // Calculate remaining elements needed
75    i -= total_count;
76  
77    // Process remaining elements one by one
78    ll current_value = left + 1;
79    for (int j = 0; j < i; ++j) {
80        // Find the lowest set bit (position of rightmost 1)
81        ll lowest_bit_mask = current_value & -current_value;
82      
83        // Add the position of the lowest set bit to the sum
84        total_sum += __builtin_ctzll(lowest_bit_mask);
85      
86        // Remove the lowest set bit from current value
87        current_value -= lowest_bit_mask;
88    }
89  
90    return total_sum;
91}
92
93// Fast modular exponentiation: compute (base^exponent) % modulo
94ll modularPower(ll base, ll exponent, ll modulo) {
95    ll result = 1 % modulo;
96    base = base % modulo;
97  
98    while (exponent > 0) {
99        // If exponent is odd, multiply result by base
100        if (exponent & 1) {
101            result = result * base % modulo;
102        }
103        // Square the base and halve the exponent
104        base = base * base % modulo;
105        exponent >>= 1;
106    }
107  
108    return result;
109}
110
111class Solution {
112public:
113    // Find products of elements for given query ranges
114    // Each query contains [left_index, right_index, modulo]
115    vector<int> findProductsOfElements(vector<vector<ll>>& queries) {
116        int query_count = queries.size();
117        vector<int> results(query_count);
118      
119        // Process each query
120        for (int i = 0; i < query_count; ++i) {
121            ll left_index = queries[i][0];
122            ll right_index = queries[i][1];
123            ll modulo = queries[i][2];
124          
125            // Calculate the sum of bit positions in the range [left, right]
126            // This sum will be the exponent for 2^sum
127            ll exponent_sum = calculateSumUpToIndex(right_index + 1) - calculateSumUpToIndex(left_index);
128          
129            // The product is 2^exponent_sum mod modulo
130            results[i] = static_cast<int>(modularPower(2, exponent_sum, modulo));
131        }
132      
133        return results;
134    }
135};
136
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 to find the largest value x such that 
82    // the count of elements up to x is less than i
83    let left = 0n;
84    let right = 1n << BigInt(MAX_BITS);
85  
86    while (left < right) {
87        const mid = (left + right + 1n) >> 1n;
88        const [count, sum] = calculateCountAndSum(mid);
89      
90        if (count < i) {
91            left = mid;
92        } else {
93            right = mid - 1n;
94        }
95    }
96  
97    // Get the sum up to the found value
98    const [totalCount, totalSum] = calculateCountAndSum(left);
99  
100    // Calculate remaining elements needed
101    i -= totalCount;
102  
103    // Process remaining elements one by one
104    let currentValue = left + 1n;
105    let resultSum = totalSum;
106  
107    for (let j = 0n; j < i; j++) {
108        // Find the lowest set bit (position of rightmost 1)
109        const lowestBitMask = currentValue & -currentValue;
110      
111        // Add the position of the lowest set bit to the sum
112        resultSum += BigInt(getLowestBitPosition(lowestBitMask));
113      
114        // Remove the lowest set bit from current value
115        currentValue -= lowestBitMask;
116    }
117  
118    return resultSum;
119}
120
121// Fast modular exponentiation: compute (base^exponent) % modulo
122function modularPower(base: ll, exponent: ll, modulo: ll): ll {
123    let result = 1n % modulo;
124    base = base % modulo;
125  
126    while (exponent > 0n) {
127        // If exponent is odd, multiply result by base
128        if ((exponent & 1n) === 1n) {
129            result = (result * base) % modulo;
130        }
131        // Square the base and halve the exponent
132        base = (base * base) % modulo;
133        exponent >>= 1n;
134    }
135  
136    return result;
137}
138
139// Find products of elements for given query ranges
140// Each query contains [leftIndex, rightIndex, modulo]
141function findProductsOfElements(queries: number[][]): number[] {
142    const queryCount = queries.length;
143    const results: number[] = new Array(queryCount);
144  
145    // Process each query
146    for (let i = 0; i < queryCount; i++) {
147        const leftIndex = BigInt(queries[i][0]);
148        const rightIndex = BigInt(queries[i][1]);
149        const modulo = BigInt(queries[i][2]);
150      
151        // Calculate the sum of bit positions in the range [left, right]
152        // This sum will be the exponent for 2^sum
153        const exponentSum = calculateSumUpToIndex(rightIndex + 1n) - calculateSumUpToIndex(leftIndex);
154      
155        // The product is 2^exponentSum mod modulo
156        results[i] = Number(modularPower(2n, exponentSum, modulo));
157    }
158  
159    return results;
160}
161

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. 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

2. 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

3. 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

4. Binary Search Boundary Conditions

The Pitfall: Incorrect binary search boundaries when finding which number contains the target index:

# WRONG: May miss edge cases
while left <= right:  # Using <= can cause infinite loops
    mid = (left + right) // 2  # Integer overflow risk in other languages

The Solution:

# CORRECT: Proper binary search for upper bound
while left < right:
    mid = (left + right + 1) >> 1  # Use +1 to avoid infinite loop
    idx, _ = calculate_bit_index_and_sum(mid)
    if idx < index:  # Strictly less than for finding upper bound
        left = mid
    else:
        right = mid - 1

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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

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 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

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

Load More