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

Final Array State After K Multiplication Operations II

Number: 3556

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, an integer k, and an integer multiplier, you must perform k operations on nums. In each operation you: • Find the minimum value x in nums (if there are ties, choose the one that appears first). • Replace x with x * multiplier. After all k operations, apply modulo 10^9+7 to every value and return the resulting array.

For example, if nums = [2,1,3,5,6], k = 5, multiplier = 2 then the operations modify the array as follows:

  1. [2, 2, 3, 5, 6]
  2. [4, 2, 3, 5, 6]
  3. [4, 4, 3, 5, 6]
  4. [4, 4, 6, 5, 6]
  5. [8, 4, 6, 5, 6] After applying modulo the final array is [8,4,6,5,6].

Key Insights

  • Every operation selects the current smallest element and “upgrades” it by multiplying with multiplier.
  • Each element’s evolution can be seen as a geometric (monotonic) sequence: a[i], a[i]multiplier, a[i](multiplier^2), …
  • The overall process is equivalent to merging these n geometric sequences in increasing order (with tie-breaking by original index).
  • Instead of simulating each operation (which is too slow when k is huge), note that the final state for each element is determined by the number of times it was “picked” (its exponent).
  • Thus, if element i is updated m_i times then its final value is a[i] * (multiplier^(m_i)) modulo 10^9+7, and the sum of all m_i is k.
  • Using a “k-way merge” idea, one can determine for each element how many “terms” from its sequence are among the k smallest values. This reduces the problem to finding, effectively by binary search on value (or its logarithm), a threshold T such that exactly k terms across all sequences are ≤ T.
  • Finally, care must be taken with ties: if several sequences have a term exactly equal to T (within precision error) then the tie‐breaking rule (first occurrence in the array) determines which sequences “don’t get” that extra multiplication.

Space and Time Complexity

Time Complexity: O(n * log(k * multiplier)) – mainly from binary search over the logarithmic space (about 60 iterations) and O(n) work per iteration. Space Complexity: O(n) – used for storing the counts for each element.

Solution

We first observe that because each element a[i] is transformed into the sequence a[i], a[i]*multiplier, a[i]*multiplier^2, …, performing k operations is the same as “merging” these sequences in sorted order. The number of times an element is updated equals the count of its sequence’s terms that belong in the first k smallest terms overall. To compute these counts without simulating k (which can be as large as 10^9) we use binary search over the logarithms of the numbers.

We define for each element the function:   count_i(X) = floor((log(X) - log(a[i])) / log(multiplier)) + 1 if X >= a[i] else 0. The total count function f(X) = Σ (over i) count_i(X) tells us how many sequence terms are ≤ X. We binary search to find the smallest X (operating in logarithmic space for numerical stability) such that f(X) ≥ k. Once this “threshold” is found, for each index i we set m_i = count_i(X). Since f(X) may count a few extra terms on the boundary (terms exactly equal to X) we then decrement the count for those indices in increasing order (to reflect the “first occurrence” rule) until the total count equals k.

Finally, each element’s final value becomes a[i] multiplied by multiplier^(m_i) modulo 10^9+7.

The key data structures are: • An array for counts (m_i) per element. • No explicit heap is needed thanks to the binary search method. The algorithm is a combination of mathematical insight (merging geometric progressions) and careful handling of ties.

Code Solutions

Below are code solutions with line‐by‐line comments in multiple languages.

import math

MOD = 10**9 + 7

def mod_exp(base, exp, mod):
    # Fast modular exponentiation
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

def finalArrayState(nums, k, multiplier):
    n = len(nums)
    # If multiplier is 1, every operation leaves the element unchanged.
    if multiplier == 1:
        return [num % MOD for num in nums]
    
    # Pre-calculate logarithms for each element.
    log_nums = [math.log(num) for num in nums]
    log_mul = math.log(multiplier)
    
    # Set binary search boundaries in log-space.
    low = min(log_nums)
    # Maximum possible log value: the max initial log plus k multiplications.
    high = max(log_nums) + k * log_mul
    eps = 1e-12  # tolerance for floating comparisons
    
    # f(mid) returns the total count of terms <= exp(mid).
    def f(mid):
        total = 0
        for ln in log_nums:
            if mid < ln:
                continue
            # Count how many times element can be multiplied so that its value is <= exp(mid)
            total += int((mid - ln) / log_mul) + 1
        return total

    # Binary search for minimal L such that f(L) >= k.
    while high - low > eps:
        mid = (low + high) / 2
        if f(mid) >= k:
            high = mid
        else:
            low = mid
    L_threshold = high  # The log value threshold corresponding to the kth term

    counts = [0] * n
    total = 0
    # Calculate counts for each element.
    for i in range(n):
        if L_threshold < log_nums[i]:
            counts[i] = 0
        else:
            counts[i] = int((L_threshold - log_nums[i]) / log_mul) + 1
        total += counts[i]

    # There may be extra counts on the boundary (terms exactly equal to threshold).
    extra = total - k
    # Decrement counts for those elements with a term exactly equal to threshold,
    # processing in array order to respect the “first occurrence” rule.
    for i in range(n):
        if extra <= 0:
            break
        if counts[i] > 0:
            # Calculate log of the last term from this element's sequence.
            term_log = log_nums[i] + (counts[i] - 1) * log_mul
            if abs(term_log - L_threshold) < eps:
                counts[i] -= 1
                extra -= 1

    # Compute final values with modular exponentiation.
    final = []
    for i in range(n):
        final_value = (nums[i] % MOD) * mod_exp(multiplier, counts[i], MOD) % MOD
        final.append(final_value)
    return final

# Example usage:
if __name__ == '__main__':
    print(finalArrayState([2,1,3,5,6], 5, 2))  # Expected: [8, 4, 6, 5, 6]
    print(finalArrayState([100000,2000], 2, 1000000))  # Expected: [999999307, 999999993]
← Back to All Questions