We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Products of Elements of Big Array

Difficulty: Hard

Problem Description

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. Given a 2D integer matrix queries, where for queries[i] = [from_i, to_i, mod_i], you should calculate (big_nums[from_i] * big_nums[from_i + 1] * ... * big_nums[to_i]) % mod_i. Return an integer array answer such that answer[i] is the answer to the i-th query.

Key Insights

  • The powerful array is derived from the binary representation of numbers, where each 1 in the binary representation corresponds to a power of two.
  • big_nums is created by concatenating powerful arrays for all positive integers in ascending order.
  • The potential range of indices for queries can be very large, requiring efficient calculation and storage of products.
  • Modular arithmetic is necessary to handle large products and prevent overflow.

Space and Time Complexity

Time Complexity: O(n * log(m)), where n is the number of queries and m is the maximum value in the queries. Space Complexity: O(n), for storing the products of subarrays or the results of queries.

Solution

To solve the problem, we employ the following steps:

  1. Powerful Array Generation: For each integer from 1 upwards, generate its powerful array by examining its binary representation.
  2. Constructing big_nums: Continuously build the big_nums array using the powerful arrays generated.
  3. Processing Queries: For each query, compute the product of the required elements from big_nums, applying the modulo operation to manage large numbers.
  4. Return Results: Store and return the results for each query.

This approach ensures that we efficiently handle the potentially large range of inputs while leveraging properties of binary representations and modular arithmetic.

Code Solutions

def get_powerful_array(x):
    powerful_array = []
    power = 1
    while x > 0:
        if x & 1:
            powerful_array.append(power)
        power <<= 1
        x >>= 1
    return powerful_array

def find_products(queries):
    max_index = max(to for _, to, _ in queries)
    big_nums = []
    
    for i in range(1, max_index + 1):
        big_nums.extend(get_powerful_array(i))
    
    results = []
    
    for from_i, to_i, mod_i in queries:
        product = 1
        for j in range(from_i, to_i + 1):
            product = (product * big_nums[j]) % mod_i
        results.append(product)
    
    return results
← Back to All Questions