Facebook Pixel

3145. Find Products of Elements of Big Array

HardBit ManipulationArrayBinary Search
Leetcode Link

Problem Description

The problem involves understanding the concept of a "powerful array" of a non-negative integer x, which is defined as the shortest sorted array of powers of two that sum up to x. This leads to creating a sequence, big_nums, by concatenating the powerful arrays for every positive integer in ascending order.

Given a 2D integer matrix queries, where each query is in the format [from_i, to_i, mod_i], the task is to calculate the product of elements from big_nums for the indices between from_i and to_i (inclusive) modulo mod_i.

Intuition

To understand the solution, we need to focus on two main observations:

  1. Powerful Array Representation: Every non-negative integer x can be expressed as a sum of distinct powers of two. This is directly represented by its binary form. For example:

    • 10 in binary is 1010, thus its powerful array is [2, 8] corresponding to the powers 1 and 8 (sum is 10).

  2. Constructing big_nums: As big_nums includes all these powerful arrays concatenated, each element in big_nums is actually a power of two.

  3. Query Results: For a given query [from_i, to_i, mod_i], the task is to compute:

    • The product of elements in big_nums from index from_i to to_i.
    • Since each element in big_nums is a power of two, the product can be represented as a power of two: 2^power.
    • Therefore, our task boils down to calculating the exponent power and performing a modulo operation: 2^power % mod_i.

By transforming the problem into one of calculating powers, we simplify the computation using properties of exponents and leveraging efficient algorithms like binary search and fast exponentiation.

Learn more about Binary Search patterns.

Solution Approach

The solution leverages a combination of binary search and bit manipulation to efficiently compute the sum of powers in the big_nums array for the given queries.

Key Steps:

  1. Precomputation:

    • The code begins by initializing two arrays, cnt and s, which are used to store precomputed results for efficient access during query processing.
    • cnt[i] stores the number of elements in the powerful arrays for numbers up to 2^i, and s[i] stores the sum of the exponents of the powers of two in these arrays.

  2. Binary Search for Index Mapping:

    • The function num_idx_and_sum(x) computes both the index and the sum of powers for numbers from 1 to x. It uses bit manipulation to extract the power of two components efficiently.

  3. Efficient Index Calculation:

    • The function f(i) uses binary search to determine the largest number whose powerful array length is less than i. This involves iterating over the bits of a number to estimate the corresponding prefix sum of powers.

  4. Query Processing:

    • For each query [from_i, to_i, mod_i], the goal is to find the product of the elements in big_nums ranging from from_i to to_i.
    • This is achieved by calculating the difference in powers using f(to_i + 1) - f(from_i), which represents the total sum of the powers of two indices.
    • The result is then computed as 2^(power) % mod_i using Python's pow() function for efficient modular exponentiation.

By precomputing the number of elements and the sum of powers for intervals of the form [2^i, 2^(i+1)-1], the solution is able to handle large intervals quickly without generating the entire big_nums array. Binary search aids in pinpointing the exact range efficiently, and modular arithmetic handles the large products gracefully.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Problem Recap: We need to compute the product of powers of two, derived from the powerful array representations of numbers, over specified index ranges and return each product modulo a given number.

Example Query: Suppose we have a small number sequence and a single query queries = [[2, 5, 10]].

  1. Powerful Array Representation:

    • For integers from 1 to 5, their powerful arrays (binary representation of each number) are:
      • 1 -> binary 1 -> [1]
      • 2 -> binary 10 -> [2]
      • 3 -> binary 11 -> [1, 2]
      • 4 -> binary 100 -> [4]
      • 5 -> binary 101 -> [1, 4]

  2. Constructing big_nums:

    • We concatenate all powerful arrays:
      • big_nums = [1, 2, 1, 2, 4, 1, 4]

  3. Query [from_i, to_i, mod_i] = [2, 5, 10]:

    • Extract the numbers from big_nums in the range from index 2 to 5:
      • Indices 2 to 5 correspond to [1, 2, 4, 1] from big_nums.

  4. Calculate the Product:

    • Compute the product 1 * 2 * 4 * 1 = 8.

  5. Modulo Operation:

    • Return 8 % 10 = 8.

Conclusion: For this query, the result is 8, derived from powers of two product modulo 10. This process, leveraging precomputed data and binary search, allows efficient query handling without explicitly forming the entire big_nums sequence.

Solution Implementation

1from typing import List
2
3# Define the maximum limit for calculations
4m = 50
5
6# Initialize count and sum arrays with base values
7cnt = [0] * (m + 1)
8s = [0] * (m + 1)
9
10# Initialize the power of two
11p = 1
12
13# Precompute the number of indexes and cumulative sums for `cnt` and `s`
14for i in range(1, m + 1):
15    cnt[i] = cnt[i - 1] * 2 + p  # Update count based on previous value
16    s[i] = s[i - 1] * 2 + p * (i - 1)  # Update sum based on previous value and index
17    p *= 2  # Double the power for the next iteration
18
19
20def num_idx_and_sum(x: int) -> tuple:
21    """
22    Calculate the number of indices and total sum based on the value of x using
23    precomputed cnt and s arrays.
24    """
25    idx = 0
26    total_sum = 0
27    while x:
28        i = x.bit_length() - 1  # Determine the highest bit position
29        idx += cnt[i]  # Add precomputed indices count
30        total_sum += s[i]  # Add precomputed sum
31        x -= 1 << i  # Reduce x by the highest power of two
32        total_sum += (x + 1) * i  # Add remaining sum contributions
33        idx += x + 1  # Add remaining index contributions
34    return idx, total_sum
35
36
37def f(i: int) -> int:
38    """
39    Find the total sum of positions required for a given index i.
40    """
41    l, r = 0, 1 << m
42    while l < r:
43        mid = (l + r + 1) >> 1  # Calculate the midpoint of the current range
44        idx, _ = num_idx_and_sum(mid)  # Get the index for the midpoint
45        if idx < i:
46            l = mid  # Move to the right half if index is less than i
47        else:
48            r = mid - 1  # Move to the left half otherwise
49
50    # Calculate the total sum after determining the exact position
51    total_sum = 0
52    idx, total_sum = num_idx_and_sum(l)
53    i -= idx
54    x = l + 1
55    for _ in range(i):
56        y = x & -x  # Extract the lowest set bit
57        total_sum += y.bit_length() - 1  # Add its position to the total sum
58        x -= y  # Remove the lowest set bit from x
59    return total_sum
60
61
62class Solution:
63    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
64        """
65        For each query, computes 2 raised to the power of the difference in sums for a range,
66        modulo the third parameter in the query.
67        """
68        return [pow(2, f(right + 1) - f(left), mod) for left, right, mod in queries]
69
1class Solution {
2    private static final int M = 50; // Define a constant M
3    private static final long[] cnt = new long[M + 1]; // Array to store counts
4    private static final long[] s = new long[M + 1]; // Array to store sums
5
6    // Static block to precompute values for cnt and s
7    static {
8        long power = 1; // Initial power of two
9        for (int i = 1; i <= M; i++) {
10            cnt[i] = cnt[i - 1] * 2 + power; // Calculate count up to i
11            s[i] = s[i - 1] * 2 + power * (i - 1); // Calculate sum up to i
12            power *= 2; // Update power for the next iteration
13        }
14    }
15
16    // Method to compute the index and total sum for a given x
17    private static long[] numIdxAndSum(long x) {
18        long idx = 0; // Index initialization
19        long totalSum = 0; // Sum initialization
20        while (x > 0) {
21            int i = Long.SIZE - Long.numberOfLeadingZeros(x) - 1; // Find the position of the highest set bit
22            idx += cnt[i]; // Add the count up to i
23            totalSum += s[i]; // Add the sum up to i
24            x -= 1L << i; // Subtract the power of two for the position
25            totalSum += (x + 1) * i; // Update the total sum with the remaining value
26            idx += x + 1; // Update the index
27        }
28        return new long[] {idx, totalSum}; // Return both index and sum as an array
29    }
30
31    // Method to find f(i) using binary search
32    private static long f(long i) {
33        long left = 0;
34        long right = 1L << M; // Initial range
35        while (left < right) {
36            long mid = (left + right + 1) >> 1; // Compute mid
37            long[] idxAndSum = numIdxAndSum(mid); // Compute index and sum for mid
38            long idx = idxAndSum[0]; // Extract index
39            if (idx < i) {
40                left = mid; // Move left boundary
41            } else {
42                right = mid - 1; // Move right boundary
43            }
44        }
45
46        long[] idxAndSum = numIdxAndSum(left); // Compute the values for left
47        long totalSum = idxAndSum[1]; // Initial total sum
48        long idx = idxAndSum[0]; // Initial index
49        i -= idx; // Adjust i
50
51        long x = left + 1; // Start processing from left + 1
52        for (int j = 0; j < i; j++) {
53            long y = x & -x; // Find the lowest set bit
54            totalSum += Long.numberOfTrailingZeros(y); // Add its bit position to the sum
55            x -= y; // Subtract y from x
56        }
57        return totalSum; // Final computed sum
58    }
59
60    // Method to process queries and find products of elements
61    public int[] findProductsOfElements(long[][] queries) {
62        int n = queries.length;
63        int[] ans = new int[n]; // Array to store results
64        for (int i = 0; i < n; i++) {
65            long left = queries[i][0];
66            long right = queries[i][1];
67            long mod = queries[i][2];
68            long power = f(right + 1) - f(left); // Calculate the power
69            ans[i] = qpow(2, power, mod); // Calculate the result using power and modular exponentiation
70        }
71        return ans; // Return the results
72    }
73
74    // Fast power calculation (modular exponentiation)
75    private int qpow(long base, long exp, long mod) {
76        long result = 1 % mod; // Initialize result
77        while (exp > 0) {
78            if ((exp & 1) == 1) {
79                result = result * base % mod; // Multiply when the current bit is set
80            }
81            base = base * base % mod; // Square the base for the next bit
82            exp >>= 1; // Shift bits right
83        }
84        return (int) result; // Return result as an integer
85    }
86}
87
1using ll = long long; // Define a shorthand for 'long long' as 'll'.
2const int M = 50; // Define a constant M representing the maximum index.
3ll count[M + 1]; // Array to store counts.
4ll sum[M + 1]; // Array to store sums.
5ll power = 1; // Initialize power for calculating powers of 2.
6
7// Lambda to initialize `count` and `sum` arrays.
8auto init = [] {
9    count[0] = 0; // Base case initialization for count.
10    sum[0] = 0; // Base case initialization for sum.
11    for (int i = 1; i <= M; ++i) {
12        count[i] = count[i - 1] * 2 + power; // Update count with twice of the previous value plus current power.
13        sum[i] = sum[i - 1] * 2 + power * (i - 1); // Update sum similarly but factoring in the index.
14        power *= 2; // Double the power for the next iteration.
15    }
16    return 0; // Return 0 to make it a proper lambda function.
17}();
18
19// Function to calculate index and sum up to a given x.
20pair<ll, ll> numIdxAndSum(ll x) {
21    ll idx = 0; // Initialize index.
22    ll totalSum = 0; // Initialize total sum.
23  
24    while (x > 0) {
25        int i = 63 - __builtin_clzll(x); // Find the highest set bit position.
26        idx += count[i]; // Add the precomputed count.
27        totalSum += sum[i]; // Add the precomputed sum.
28        x -= 1LL << i; // Subtract the found power of 2 from x.
29        totalSum += (x + 1) * i; // Add to the total sum based on the remaining x.
30        idx += x + 1; // Increment index accordingly.
31    }
32  
33    return make_pair(idx, totalSum); // Return the pair of index and sum.
34}
35
36// Function to calculate the sum of f(i).
37ll f(ll i) {
38    // Initialize binary search bounds.
39    ll left = 0;
40    ll right = 1LL << M;
41  
42    // Perform binary search to find the boundary.
43    while (left < right) {
44        ll mid = (left + right + 1) >> 1; // Calculate the midpoint.
45        auto idxAndSum = numIdxAndSum(mid); // Get index and sum for midpoint.
46        ll idx = idxAndSum.first; // Extract index value.
47      
48        if (idx < i) {
49            left = mid; // Narrow down search to the right half.
50        } else {
51            right = mid - 1; // Narrow down search to the left half.
52        }
53    }
54  
55    auto idxAndSum = numIdxAndSum(left);
56    ll totalSum = idxAndSum.second;
57    ll idx = idxAndSum.first;
58  
59    i -= idx; // Adjust target index.
60    ll x = left + 1; // Start from the next integer after left.
61  
62    for (int j = 0; j < i; ++j) {
63        ll y = x & -x; // Find the smallest set bit.
64        totalSum += __builtin_ctzll(y); // Add the zero count to the sum.
65        x -= y; // Remove the smallest bit.
66    }
67  
68    return totalSum; // Return the resultant sum.
69}
70
71// Function for fast modular exponentiation.
72ll qpow(ll base, ll exponent, ll mod) {
73    ll result = 1 % mod; // Initialize result with modular 1.
74    base %= mod; // Ensure base is within mod value.
75  
76    while (exponent > 0) {
77        if (exponent & 1) {
78            result = result * base % mod; // Multiply result by base when exponent bit is set.
79        }
80        base = base * base % mod; // Square the base under mod.
81        exponent >>= 1; // Shift exponent to right to process next bit.
82    }
83  
84    return result; // Return result of modular exponentiation.
85}
86
87class Solution {
88public:
89    // Method to process queries and find products of elements.
90    vector<int> findProductsOfElements(vector<vector<ll>>& queries) {
91        int n = queries.size(); // Get number of queries.
92        vector<int> answers(n); // Initialize answer vector.
93      
94        for (int i = 0; i < n; ++i) {
95            ll left = queries[i][0];
96            ll right = queries[i][1];
97            ll mod = queries[i][2];
98          
99            ll power = f(right + 1) - f(left); // Calculate power difference.
100            answers[i] = static_cast<int>(qpow(2, power, mod)); // Calculate power of 2 under mod and store.
101        }
102      
103        return answers; // Return resulting answers.
104    }
105};
106
1type ll = number; // Define a shorthand for 'number' as 'll'.
2
3const M: number = 50; // Define a constant M representing the maximum index.
4const count: ll[] = new Array(M + 1).fill(0); // Array to store counts.
5const sum: ll[] = new Array(M + 1).fill(0); // Array to store sums.
6let power: ll = 1; // Initialize power for calculating powers of 2.
7
8// Lambda-like initialization for `count` and `sum` arrays.
9const init = (() => {
10    count[0] = 0; // Base case initialization for count.
11    sum[0] = 0; // Base case initialization for sum.
12    for (let i = 1; i <= M; ++i) {
13        count[i] = count[i - 1] * 2 + power; // Update count with twice of the previous value plus current power.
14        sum[i] = sum[i - 1] * 2 + power * (i - 1); // Update sum similarly but factoring in the index.
15        power *= 2; // Double the power for the next iteration.
16    }
17})();
18
19// Function to calculate index and sum up to a given x.
20function numIdxAndSum(x: ll): [ll, ll] {
21    let idx: ll = 0; // Initialize index.
22    let totalSum: ll = 0; // Initialize total sum.
23
24    while (x > 0) {
25        const i: number = 63 - Math.clz32(x); // Find the highest set bit position.
26        idx += count[i]; // Add the precomputed count.
27        totalSum += sum[i]; // Add the precomputed sum.
28        x -= 1 << i; // Subtract the found power of 2 from x.
29        totalSum += (x + 1) * i; // Add to the total sum based on the remaining x.
30        idx += x + 1; // Increment index accordingly.
31    }
32
33    return [idx, totalSum]; // Return the pair of index and sum.
34}
35
36// Function to calculate the sum of f(i).
37function f(i: ll): ll {
38    // Initialize binary search bounds.
39    let left: ll = 0;
40    let right: ll = 1 << M;
41
42    // Perform binary search to find the boundary.
43    while (left < right) {
44        const mid: ll = (left + right + 1) >> 1; // Calculate the midpoint.
45        const [midIdx, midSum] = numIdxAndSum(mid); // Get index and sum for midpoint.
46
47        if (midIdx < i) {
48            left = mid; // Narrow down the search to the right half.
49        } else {
50            right = mid - 1; // Narrow down the search to the left half.
51        }
52    }
53
54    const [finalIdx, finalSum] = numIdxAndSum(left);
55    let totalSum: ll = finalSum;
56    let idx: ll = finalIdx;
57
58    i -= idx; // Adjust target index.
59    let x: ll = left + 1; // Start from the next integer after left.
60
61    for (let j = 0; j < i; ++j) {
62        const y: ll = x & -x; // Find the smallest set bit.
63        totalSum += Math.clz32(-y) - 31; // Add the zero count to the sum.
64        x -= y; // Remove the smallest bit.
65    }
66
67    return totalSum; // Return the resultant sum.
68}
69
70// Function for fast modular exponentiation.
71function qpow(base: ll, exponent: ll, mod: ll): ll {
72    let result: ll = 1 % mod; // Initialize result with modular 1.
73    base %= mod; // Ensure base is within the mod value.
74
75    while (exponent > 0) {
76        if (exponent & 1) {
77            result = (result * base) % mod; // Multiply result by base when exponent bit is set.
78        }
79        base = (base * base) % mod; // Square the base under mod.
80        exponent >>= 1; // Shift exponent to right to process the next bit.
81    }
82
83    return result; // Return result of modular exponentiation.
84}
85
86// Function to process queries and find products of elements.
87function findProductsOfElements(queries: ll[][]): number[] {
88    const n: number = queries.length; // Get number of queries.
89    const answers: number[] = []; // Initialize answer vector.
90
91    for (let i = 0; i < n; ++i) {
92        const left: ll = queries[i][0];
93        const right: ll = queries[i][1];
94        const mod: ll = queries[i][2];
95
96        const power: ll = f(right + 1) - f(left); // Calculate power difference.
97        answers.push(qpow(2, power, mod)); // Calculate power of 2 under mod and store.
98    }
99
100    return answers; // Return resulting answers.
101}
102

Time and Space Complexity

The time complexity of the Solution.findProductsOfElements method is O(q \times \log M). This complexity arises because for each query, the method calls the function f twice, and each call to f involves a binary search on the range [0, 1 << m), where m is set to 50. The binary search requires O(\log M) operations, where M is the upper bound value for the numbers being processed. As the binary search is combined with the arithmetic operations within the f function, the overall complexity for processing q queries becomes O(q \times \log M).

The space complexity is O(\log M), which is primarily due to the storage requirements for the binary representation and auxiliary space during the operations within each query's function executions. While iterative approaches generally have low space requirements, the processing of bit manipulations and number storage contributes to this complexity.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

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

Load More