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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Products of Elements of Big Array

Number: 3411

Difficulty: Hard

Paid? No

Companies: IBM

Problem Description

We are given an infinite “big” array that is built by concatenating, for every positive integer i in increasing order, its “powerful array” – the unique sorted array of powers of two that sum up to i (equivalently, the powers-of‑two corresponding to the set bits in i). For example, for i = 13 (binary 1101) the powerful array is [1, 4, 8]. Then, for an input query [from, to, mod] we need to compute (big_nums[from] * big_nums[from+1] * … * big_nums[to]) % mod. The query indices (from and to) refer to positions inside this flattened array. Note that because the “big array” is constructed indirectly (by processing every positive integer) and the query indices can be huge (up to 10^15), we must solve the problem without explicitly forming the array.

Key Insights

  • The “powerful array” for a number i is determined by its set bits. If the k-th bit is set then i contributes a term of 2^k.
  • Multiplying the elements (each a power of two) results in a product that is itself a power of two; in particular, the product for a single number i equals 2^(sum of indices of its set bits).
  • The flattened big array is a concatenation of all powerful arrays for i = 1, 2, 3, …, and its length up to any i is F(i) = sum_{j=1}^{i} popcount(j).
  • Given a query range [from, to] (1-indexed), the challenge is to “invert” F(i) using binary search to determine which integer’s powerful array covers a given flattened index.
  • For a query that might start or end in the middle of a number’s powerful array, we must compute the partial contribution. For a complete integer i, its entire product contribution is 2^(sum of set-bit positions) and for a partial contribution we sum just the exponents of the selected bits (remember that the bits appear sorted in increasing order).
  • Finally, the overall product over any query range is 2^(total_exponent) modulo mod, so the problem reduces to efficiently computing this total exponent.

Space and Time Complexity

Time Complexity: O(Q * (log(max_n) * log(max_n_bits))) where Q is the number of queries; each query performs two binary searches (to invert F(.)) and does bit‐operations over O(log(n)) bits. Space Complexity: O(1) extra space aside from the recursion/iteration stack used in helper functions.

Solution

We solve the problem in the following steps:

  1. Define a helper function to compute F(n) = sum_{i=1}^{n} popcount(i) using a recursive formula. (This is the standard “count total set bits” function.)
  2. To “invert” the mapping F(n) (i.e. to find for a given query index pos which is the smallest n satisfying F(n) ≥ pos), we use binary search.
  3. Define a helper S(n) that computes the total exponent contribution for numbers 1..n, where for each number i the contribution is the sum of indices of its set bits. This can be computed by summing over each bit position k the value k * (number of integers in [1, n] that have the k‑th bit set).
  4. For a given query [L, R, mod]:
    • Use binary search to locate the integer (say nL) that contains the L‑th element in the big array and find the offset (within nL’s sorted powerful array) of L.
    • Similarly locate the integer (say nR) and offset for R.
    • If both indices fall within the same number, simply sum the exponents corresponding to the bits in the partial subarray.
    • Otherwise, compute: • The partial contribution for the tail of nL (from the offset to the end of its powerful array). • The full contributions for every integer between nL+1 and nR–1 using S(nR-1) – S(nL). • The partial contribution for nR (from the beginning of its powerful array to the given offset).
  5. The final answer is 2^(total_exponent) mod mod.

Data structures used include helper functions (for recursing on n in F(n) and S(n)) and standard binary search. The “trick” is to map an index in the flattened array back to the originating integer and which bits from that integer are used, and to convert the multiplication of many powers of two to a modular exponentiation.

Code Solutions

Below are code solutions in Python, JavaScript, C++ and Java with line‐by‐line comments.

# Python solution

def sum_set_bits(n):
    # Returns F(n): total number of set bits for all numbers from 1 to n.
    if n == 0:
        return 0
    # m = floor(log2(n))
    m = n.bit_length() - 1
    p = 1 << m  # 2^m
    # m * 2^(m-1): bits count from numbers 1 to 2^m - 1;
    # then add the most significant bit count and recursively count remainder.
    return m * (p >> 1) + (n - p + 1) + sum_set_bits(n - p)

def find_number_by_index(target):
    # Binary search to find the smallest n such that sum_set_bits(n) >= target.
    lo, hi = 1, 10**18  # hi is chosen large enough
    while lo < hi:
        mid = (lo + hi) // 2
        if sum_set_bits(mid) < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def get_powerful_array_bits(num):
    # Returns a list of the exponents (k) for which the k-th bit is set in 'num'.
    bits = []
    k = 0
    while (1 << k) <= num:
        if num & (1 << k):
            bits.append(k)
        k += 1
    return bits  # Already in increasing order

def sum_exponents_partial(num, start_idx, end_idx):
    # Sum the exponents for the partial powerful array of num corresponding
    # to indices [start_idx, end_idx] (inclusive)
    bits = get_powerful_array_bits(num)
    return sum(bits[start_idx:end_idx+1])

def count_bit_set(n, k):
    # Counts how many numbers in [1, n] have the k-th bit set.
    blockSize = 1 << (k + 1)
    fullBlocks = n // blockSize
    count = fullBlocks * (1 << k)
    remainder = n % blockSize
    count += max(0, remainder - (1 << k) + 1)
    return count

def S(n):
    # S(n): total exponent sum for numbers from 1 to n,
    # where each number i contributes sum of k for every set bit at position k.
    total = 0
    # iterate over bit positions; since n can be huge, we iterate up to 60 bits.
    for k in range(61):
        total += k * count_bit_set(n, k)
    return total

def solve_queries(queries):
    answers = []
    for L, R, mod in queries:
        # Find number and offset for position L
        nL = find_number_by_index(L)
        prev_count_nL = sum_set_bits(nL - 1) if nL > 1 else 0
        offsetL = L - prev_count_nL - 1  # 0-indexed position within nL's powerful array

        # Find number and offset for position R
        nR = find_number_by_index(R)
        prev_count_nR = sum_set_bits(nR - 1) if nR > 1 else 0
        offsetR = R - prev_count_nR - 1  # 0-indexed

        total_exponent = 0
        if nL == nR:
            # Both indices fall within the same number's powerful array.
            total_exponent = sum_exponents_partial(nL, offsetL, offsetR)
        else:
            # Partial contribution from nL: from offsetL to end of its powerful array.
            bits_nL = get_powerful_array_bits(nL)
            total_exponent += sum(bits_nL[offsetL:])

            # Partial contribution from nR: from 0 to offsetR.
            bits_nR = get_powerful_array_bits(nR)
            total_exponent += sum(bits_nR[:offsetR+1])

            # Full numbers between nL+1 and nR-1.
            if nR - 1 >= nL + 1:
                total_exponent += S(nR - 1) - S(nL)
        # Compute the product as 2^(total_exponent) mod mod
        answer = pow(2, total_exponent, mod)
        answers.append(answer)
    return answers

# Example Usage:
queries1 = [[1, 3, 7]]
print(solve_queries(queries1))  # Expected output: [4]
queries2 = [[2, 5, 3], [7, 7, 4]]
print(solve_queries(queries2))  # Expected output: [2, 2]
← Back to All Questions