# Final Array State After K Multiplication Operations II
**Difficulty:** HARD
[External](https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-ii)
Canonical: https://scaleengineer.com/dsa/problems/final-array-state-after-k-multiplication-operations-ii
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
You are given an integer array `nums`, an integer `k`, and an integer `multiplier`.

You need to perform `k` operations on `nums`. In each operation:

* Find the **minimum** value `x` in `nums`. If there are multiple occurrences of the minimum value, select the one that appears **first**.
* Replace the selected minimum value `x` with `x * multiplier`.

After the `k` operations, apply **modulo** `109 + 7` to every value in `nums`.

Return an integer array denoting the _final state_ of `nums` after performing all `k` operations and then applying the modulo.

**Example 1:**

**Input:** nums = \[2,1,3,5,6\], k = 5, multiplier = 2

**Output:** \[8,4,6,5,6\]

**Explanation:**

| Operation             | Result            |
| --------------------- | ----------------- |
| After operation 1     | \[2, 2, 3, 5, 6\] |
| After operation 2     | \[4, 2, 3, 5, 6\] |
| After operation 3     | \[4, 4, 3, 5, 6\] |
| After operation 4     | \[4, 4, 6, 5, 6\] |
| After operation 5     | \[8, 4, 6, 5, 6\] |
| After applying modulo | \[8, 4, 6, 5, 6\] |

**Example 2:**

**Input:** nums = \[100000,2000\], k = 2, multiplier = 1000000

**Output:** \[999999307,999999993\]

**Explanation:**

| Operation             | Result                       |
| --------------------- | ---------------------------- |
| After operation 1     | \[100000, 2000000000\]       |
| After operation 2     | \[100000000000, 2000000000\] |
| After applying modulo | \[999999307, 999999993\]     |

**Constraints:**

* `1 <= nums.length <= 104`
* `1 <= nums[i] <= 109`
* `1 <= k <= 109`
* `1 <= multiplier <= 106`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It iterates `k` times, and in each iteration, it performs a linear scan of the array to find the minimum element, then updates it. This is the most straightforward way to conceptualize the solution but is not practical given the constraints.
**Time:** O(k * n) - The outer loop runs `k` times, and the inner loop to find the minimum runs `n` times. With `k` up to `10^9` and `n` up to `10^4`, this is far too slow. · **Space:** O(n) or O(1) - O(n) if a copy of the array is made to handle large numbers (like `long[]`), otherwise O(1) if the original array can be modified and its data type is sufficient (which is not the case here due to potential overflow).
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will time out for large values of `k`.
### Explanation
The brute-force method follows the problem statement literally. We run a loop for `k` iterations. Inside this loop, we search the entire array to find the minimum value and its first occurring index. This search takes linear time, `O(n)`, where `n` is the length of the array. Once found, we multiply this minimum value by the `multiplier`. This process is repeated `k` times. Since the values can become very large, we should use a data type that can handle large numbers, like `long` in Java, to avoid overflow during multiplication. After all `k` operations are complete, a final pass is made over the array to apply the modulo `10^9 + 7` to each element.

```java
class Solution {
    public int[] finalArray(int[] nums, int k, int multiplier) {
        int n = nums.length;
        long[] longNums = new long[n];
        for (int i = 0; i < n; i++) {
            longNums[i] = nums[i];
        }

        for (int i = 0; i < k; i++) {
            int minIndex = -1;
            long minVal = Long.MAX_VALUE;

            for (int j = 0; j < n; j++) {
                if (longNums[j] < minVal) {
                    minVal = longNums[j];
                    minIndex = j;
                }
            }

            if (minIndex != -1) {
                longNums[minIndex] *= multiplier;
            }
        }

        int[] result = new int[n];
        int MOD = 1_000_000_007;
        for (int i = 0; i < n; i++) {
            result[i] = (int)(longNums[i] % MOD);
        }

        return result;
    }
}
```
### Algorithm
- Loop `k` times from `i = 0` to `k-1`.
- In each iteration, find the index of the minimum element in the `nums` array.
  - Initialize `min_val` to `infinity` and `min_idx` to `-1`.
  - Iterate through the `nums` array from `j = 0` to `n-1`.
  - If `nums[j]` is less than `min_val`, update `min_val = nums[j]` and `min_idx = j`.
- After finding the minimum element at `min_idx`, update it: `nums[min_idx] = nums[min_idx] * multiplier`.
- After the main loop finishes, iterate through the `nums` array one last time.
- Apply modulo `10^9 + 7` to each element: `nums[i] = nums[i] % (10^9 + 7)`.
- Return the modified `nums` array.

## Min-Heap Simulation
To optimize the process of finding the minimum element in each step, we can use a min-heap (Priority Queue). A min-heap allows us to retrieve the minimum element in `O(log n)` time instead of `O(n)`. We store pairs of `(value, index)` in the heap to respect the tie-breaking rule. While this is a significant improvement over the brute-force approach, it still simulates each of the `k` operations individually.
**Time:** O((n+k) log n) - Building the heap takes `O(n log n)`. Each of the `k` operations takes `O(log n)`. Reconstructing the array takes `O(n log n)`. The total is dominated by the `k` operations. This is still too slow if `k` is large. · **Space:** O(n) - To store `n` elements in the priority queue.
**Pros:** Much faster than brute-force for finding the minimum element in each step.
**Cons:** Still too slow for large values of `k` as it performs one operation at a time.; Requires using `BigInteger` for values to prevent overflow, which adds overhead to operations.
### Explanation
The bottleneck in the brute-force approach is the repeated linear scan to find the minimum. A min-heap is the perfect data structure to speed this up. We can build a min-heap containing all the numbers from the input array. To handle ties where the element with the smaller original index should be chosen, we store pairs of `(value, index)` in the heap. The heap's comparator will prioritize smaller values, and for equal values, it will prioritize smaller indices.

The simulation then proceeds for `k` steps. In each step, we extract the minimum element from the heap, multiply its value by the `multiplier`, and insert the updated pair back into the heap. Each such operation (extraction and insertion) takes `O(log n)` time. After `k` operations, we reconstruct the final array from the elements in the heap.

Note that the values can grow extremely large, exceeding the capacity of `long`. A `BigInteger` is required to store the values in the heap to prevent overflow.

```java
import java.math.BigInteger;
import java.util.PriorityQueue;

class Solution {
    public int[] finalArray(int[] nums, int k, int multiplier) {
        int n = nums.length;
        // A min-heap storing {value, original_index}
        // BigInteger is needed as values can get very large.
        PriorityQueue<Object[]> pq = new PriorityQueue<>((a, b) -> {
            BigInteger valA = (BigInteger) a[0];
            BigInteger valB = (BigInteger) b[0];
            int idxA = (int) a[1];
            int idxB = (int) b[1];
            int cmp = valA.compareTo(valB);
            if (cmp != 0) {
                return cmp;
            }
            return Integer.compare(idxA, idxB);
        });

        for (int i = 0; i < n; i++) {
            pq.add(new Object[]{new BigInteger(String.valueOf(nums[i])), i});
        }

        BigInteger bigMultiplier = new BigInteger(String.valueOf(multiplier));
        for (int i = 0; i < k; i++) {
            Object[] top = pq.poll();
            BigInteger val = (BigInteger) top[0];
            int idx = (int) top[1];
            BigInteger newVal = val.multiply(bigMultiplier);
            pq.add(new Object[]{newVal, idx});
        }

        BigInteger[] finalValues = new BigInteger[n];
        while (!pq.isEmpty()) {
            Object[] top = pq.poll();
            BigInteger val = (BigInteger) top[0];
            int idx = (int) top[1];
            finalValues[idx] = val;
        }

        int[] result = new int[n];
        int MOD = 1_000_000_007;
        BigInteger bigMod = new BigInteger(String.valueOf(MOD));
        for (int i = 0; i < n; i++) {
            result[i] = finalValues[i].mod(bigMod).intValue();
        }

        return result;
    }
}
```
### Algorithm
- To handle the tie-breaking rule (smallest index first), we store pairs of `(value, original_index)`.
- Create a Min-Heap (PriorityQueue in Java) that compares elements first by `value`, then by `index`.
- Insert all initial `(nums[i], i)` pairs into the heap.
- Loop `k` times:
  - Extract the minimum pair `(val, idx)` from the heap.
  - Calculate the new value: `new_val = val * multiplier`.
  - Insert the new pair `(new_val, idx)` back into the heap.
- After `k` operations, the heap contains the final state.
- Create a result array of size `n`.
- Poll all elements from the heap and place their values in the result array at their corresponding original indices.
- Apply modulo `10^9 + 7` to each element in the result array.

## Binary Search on the Final State
Since `k` can be enormous, simulating each operation is infeasible. The key is to analyze the properties of the final array. The greedy nature of the operations (always picking the minimum) leads to a state where all final values are relatively close to each other. This property allows us to determine the number of multiplications each element receives without simulating the process. We can use binary search to find the 'level' to which all numbers are raised. This transforms the problem from a lengthy simulation into a search problem, which is much more efficient.
**Time:** O(n log n + n log k) - The binary search part takes `O(100 * n) = O(n)`. Calculating initial counts is `O(n)`. Distributing remaining operations requires sorting, which is `O(n log n)`. The final computation involves `n` modular exponentiations, each taking `O(log k)` time (since counts can be up to `k`). The total complexity is dominated by sorting and modular exponentiation. · **Space:** O(n) - To store the counts for each number and the pairs for sorting to distribute remaining operations.
**Pros:** Highly efficient and can handle very large `k`.; Avoids simulating individual operations, leading to a much better time complexity.
**Cons:** More complex to understand and implement.; Relies on floating-point arithmetic (`log`), which can have precision issues, though typically manageable with `double` and enough binary search iterations.
### Explanation
This approach avoids simulation by finding the final state analytically. The core idea is that the `k` multiplications are distributed among the `n` numbers in a way that keeps their final values close. This means `final_value_i < final_value_j * multiplier` for any `i, j`. Taking `log_multiplier` on both sides, we find that `log_m(final_value_i)` for all `i` must lie in an interval of length 1.

We can binary search for the lower bound of this interval, let's call it `T`. For a given `T`, we can calculate the minimum number of multiplications `c_i` needed for each `nums[i]` to make `log_m(nums[i] * multiplier^{c_i}) >= T`. This count is `c_i = ceil(T - log_m(nums[i]))`. We sum these `c_i`'s to get a total `ops_needed`. If `ops_needed <= k`, it means `T` is a possible level, and we can try for a higher one. Otherwise, `T` is too high.

After the binary search finds the optimal `T`, we calculate the initial counts `c_i`. The sum of these counts will be less than or equal to `k`. Any remaining operations `k_rem` are distributed one by one to the elements that are currently smallest. We identify these by sorting based on their current logarithmic value `log_m(nums[i]) + c_i`.

Finally, with the definitive count of multiplications `c_i` for each `nums[i]`, we compute `(nums[i] * power(multiplier, c_i)) % MOD` using modular exponentiation.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    private static final int MOD = 1_000_000_007;

    public int[] finalArray(int[] nums, int k, int multiplier) {
        int n = nums.length;
        if (multiplier == 1) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = nums[i] % MOD;
            }
            return result;
        }

        double logMultiplier = Math.log(multiplier);

        double low = 0, high = k + 40; // A safe upper bound for the target level
        for(int iter = 0; iter < 100; iter++) { // 100 iterations for precision
            double mid = low + (high - low) / 2;
            if (check(mid, nums, k, logMultiplier)) {
                low = mid;
            } else {
                high = mid;
            }
        }

        long[] counts = new long[n];
        long opsUsed = 0;
        for (int i = 0; i < n; i++) {
            double logNum = Math.log(nums[i]);
            long c = (long) Math.ceil((low * logMultiplier - logNum) / logMultiplier);
            if (c > 0) {
                counts[i] = c;
                opsUsed += c;
            }
        }

        long kRem = k - opsUsed;
        
        if (kRem > 0) {
            Double[][] sortedLogs = new Double[n][2];
            for (int i = 0; i < n; i++) {
                sortedLogs[i][0] = (Math.log(nums[i]) + counts[i] * logMultiplier) / logMultiplier;
                sortedLogs[i][1] = (double) i;
            }

            Arrays.sort(sortedLogs, Comparator.comparingDouble(a -> a[0]));

            for (int i = 0; i < kRem; i++) {
                int originalIndex = sortedLogs[i][1].intValue();
                counts[originalIndex]++;
            }
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            long p = power(multiplier, counts[i], MOD);
            result[i] = (int) (((long) nums[i] * p) % MOD);
        }

        return result;
    }

    private boolean check(double T, int[] nums, long k, double logMultiplier) {
        long opsNeeded = 0;
        for (int num : nums) {
            double logNum = Math.log(num);
            // We need num * mult^c >= T_val, where log(T_val) = T * logMultiplier
            // c >= T - log_m(num)
            double ops = (T * logMultiplier - logNum) / logMultiplier;
            if (ops > 0) {
                opsNeeded += (long) Math.ceil(ops);
            }
            if (opsNeeded > k) {
                return false;
            }
        }
        return true;
    }

    private long power(long base, long exp, int mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- **Handle Edge Case**: If `multiplier` is 1, the array values never change. Simply apply modulo to the initial array and return.
- **Key Insight**: After many operations, the final values `v_i` become relatively close. Specifically, `max(v) < min(v) * multiplier`. This implies that their logarithms to the base `multiplier`, `log_m(v_i)`, all lie within an interval of length 1. Let this be `[T, T+1)`.
- **Binary Search**: We can binary search for this target "level" `T`. The search space for `T` can be from `0` to `k + log_m(max(nums))`. We perform binary search for a fixed number of iterations (e.g., 100) to find a precise `T`.
  - The `check(T)` function calculates the total operations needed to bring every `nums[i]` to a level of at least `T`. For each `num`, the operations needed is `c_i = ceil(T - log_m(num))`. If `sum(c_i) <= k`, it means `T` is achievable.
- **Calculate Final Counts**: After finding the optimal `T`, calculate the base number of multiplications for each element: `c_i = ceil(T - log_m(nums[i]))`.
- **Distribute Remainder**: The sum of these `c_i`'s, `k_used`, might be less than `k`. The remaining `k_rem = k - k_used` operations must be given to the `k_rem` elements that are currently smallest. We find these by sorting pairs of `(log_m(nums[i]) + c_i, i)` and picking the first `k_rem`.
- **Compute Final Array**: With the final counts `c_i` for each element, calculate the final value `(nums[i] * (multiplier ^ c_i)) % MOD`. Use modular exponentiation for `multiplier ^ c_i` to handle large powers efficiently.

# Solutions
### Java

```java
class Solution {
public
  int[] getFinalState(int[] nums, int k, int multiplier) {
    if (multiplier == 1) {
      return nums;
    }
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b)->a[0] == b[0] ? Long.compare(a[1], b[1])
                                                 : Long.compare(a[0], b[0]));
    int n = nums.length;
    int m = Arrays.stream(nums).max().getAsInt();
    for (int i = 0; i < n; ++i) {
      pq.offer(new long[]{nums[i], i});
    }
    for (; k > 0 && pq.peek()[0] < m; --k) {
      long[] p = pq.poll();
      p[0] *= multiplier;
      pq.offer(p);
    }
    final int mod = (int)1 e9 + 7;
    for (int i = 0; i < n; ++i) {
      long[] p = pq.poll();
      long x = p[0];
      int j = (int)p[1];
      nums[j] = (int)((x % mod) *
                      qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);
    }
    return nums;
  }
private
  int qpow(long a, long n, long mod) {
    long ans = 1 % mod;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getFinalState(vector<int> &nums, int k, int multiplier) {
    if (multiplier == 1) {
      return nums;
    }
    using ll = long long;
    using pli = pair<ll, int>;
    auto cmp = [](const pli &a, const pli &b) {
      if (a.first == b.first) {
        return a.second > b.second;
      }
      return a.first > b.first;
    };
    priority_queue<pli, vector<pli>, decltype(cmp)> pq(cmp);
    int n = nums.size();
    int m = *max_element(nums.begin(), nums.end());
    for (int i = 0; i < n; ++i) {
      pq.emplace(nums[i], i);
    }
    while (k > 0 && pq.top().first < m) {
      auto p = pq.top();
      pq.pop();
      p.first *= multiplier;
      pq.emplace(p);
      --k;
    }
    auto qpow = [&](ll a, ll n, ll mod) {
      ll ans = 1 % mod;
      a = a % mod;
      while (n > 0) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
      }
      return ans;
    };
    const int mod = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
      auto p = pq.top();
      pq.pop();
      long long x = p.first;
      int j = p.second;
      nums[j] = static_cast<int>(
          (x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);
    }
    return nums;
  }
};

```

### Python

```python
class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: if multiplier == 1: return nums pq = [(x, i) for i, x in enumerate(nums)] heapify(pq) m = max(nums) while k and pq[0][0] < m: x, i = heappop(pq) heappush(pq, (x * multiplier, i)) k -= 1 n = len(nums) mod = 10 ** 9 + 7 pq . sort() for i, (x, j) in enumerate(pq): nums[j] = x * pow(multiplier, k // n + int(i < k % n), mod) % mod return nums

```