Final Array State After K Multiplication Operations II

Hard

#2899Time: 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).

Data structures

Array Heap (Priority Queue)

Prompt

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 10⁹ + 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 <= 10⁴
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹
1 <= multiplier <= 10⁶

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int[] finalArray(int[] nums, int k, int multiplier) {3        int n = nums.length;4        long[] longNums = new long[n];5        for (int i = 0; i < n; i++) {6            longNums[i] = nums[i];7        }8 9        for (int i = 0; i < k; i++) {10            int minIndex = -1;11            long minVal = Long.MAX_VALUE;12 13            for (int j = 0; j < n; j++) {14                if (longNums[j] < minVal) {15                    minVal = longNums[j];16                    minIndex = j;17                }18            }19 20            if (minIndex != -1) {21                longNums[minIndex] *= multiplier;22            }23        }24 25        int[] result = new int[n];26        int MOD = 1_000_000_007;27        for (int i = 0; i < n; i++) {28            result[i] = (int)(longNums[i] % MOD);29        }30 31        return result;32    }33}

Complexity

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).

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient and will time out for large values of k.

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.

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.

Walkthrough

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.

1import java.math.BigInteger;2import java.util.PriorityQueue;3 4class Solution {5    public int[] finalArray(int[] nums, int k, int multiplier) {6        int n = nums.length;7        // A min-heap storing {value, original_index}8        // BigInteger is needed as values can get very large.9        PriorityQueue<Object[]> pq = new PriorityQueue<>((a, b) -> {10            BigInteger valA = (BigInteger) a[0];11            BigInteger valB = (BigInteger) b[0];12            int idxA = (int) a[1];13            int idxB = (int) b[1];14            int cmp = valA.compareTo(valB);15            if (cmp != 0) {16                return cmp;17            }18            return Integer.compare(idxA, idxB);19        });20 21        for (int i = 0; i < n; i++) {22            pq.add(new Object[]{new BigInteger(String.valueOf(nums[i])), i});23        }24 25        BigInteger bigMultiplier = new BigInteger(String.valueOf(multiplier));26        for (int i = 0; i < k; i++) {27            Object[] top = pq.poll();28            BigInteger val = (BigInteger) top[0];29            int idx = (int) top[1];30            BigInteger newVal = val.multiply(bigMultiplier);31            pq.add(new Object[]{newVal, idx});32        }33 34        BigInteger[] finalValues = new BigInteger[n];35        while (!pq.isEmpty()) {36            Object[] top = pq.poll();37            BigInteger val = (BigInteger) top[0];38            int idx = (int) top[1];39            finalValues[idx] = val;40        }41 42        int[] result = new int[n];43        int MOD = 1_000_000_007;44        BigInteger bigMod = new BigInteger(String.valueOf(MOD));45        for (int i = 0; i < n; i++) {46            result[i] = finalValues[i].mod(bigMod).intValue();47        }48 49        return result;50    }51}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    private static final int MOD = 1_000_000_007;6 7    public int[] finalArray(int[] nums, int k, int multiplier) {8        int n = nums.length;9        if (multiplier == 1) {10            int[] result = new int[n];11            for (int i = 0; i < n; i++) {12                result[i] = nums[i] % MOD;13            }14            return result;15        }16 17        double logMultiplier = Math.log(multiplier);18 19        double low = 0, high = k + 40; // A safe upper bound for the target level20        for(int iter = 0; iter < 100; iter++) { // 100 iterations for precision21            double mid = low + (high - low) / 2;22            if (check(mid, nums, k, logMultiplier)) {23                low = mid;24            } else {25                high = mid;26            }27        }28 29        long[] counts = new long[n];30        long opsUsed = 0;31        for (int i = 0; i < n; i++) {32            double logNum = Math.log(nums[i]);33            long c = (long) Math.ceil((low * logMultiplier - logNum) / logMultiplier);34            if (c > 0) {35                counts[i] = c;36                opsUsed += c;37            }38        }39 40        long kRem = k - opsUsed;41        42        if (kRem > 0) {43            Double[][] sortedLogs = new Double[n][2];44            for (int i = 0; i < n; i++) {45                sortedLogs[i][0] = (Math.log(nums[i]) + counts[i] * logMultiplier) / logMultiplier;46                sortedLogs[i][1] = (double) i;47            }48 49            Arrays.sort(sortedLogs, Comparator.comparingDouble(a -> a[0]));50 51            for (int i = 0; i < kRem; i++) {52                int originalIndex = sortedLogs[i][1].intValue();53                counts[originalIndex]++;54            }55        }56 57        int[] result = new int[n];58        for (int i = 0; i < n; i++) {59            long p = power(multiplier, counts[i], MOD);60            result[i] = (int) (((long) nums[i] * p) % MOD);61        }62 63        return result;64    }65 66    private boolean check(double T, int[] nums, long k, double logMultiplier) {67        long opsNeeded = 0;68        for (int num : nums) {69            double logNum = Math.log(num);70            // We need num * mult^c >= T_val, where log(T_val) = T * logMultiplier71            // c >= T - log_m(num)72            double ops = (T * logMultiplier - logNum) / logMultiplier;73            if (ops > 0) {74                opsNeeded += (long) Math.ceil(ops);75            }76            if (opsNeeded > k) {77                return false;78            }79        }80        return true;81    }82 83    private long power(long base, long exp, int mod) {84        long res = 1;85        base %= mod;86        while (exp > 0) {87            if (exp % 2 == 1) res = (res * base) % mod;88            base = (base * base) % mod;89            exp /= 2;90        }91        return res;92    }93}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] getFinalState(int[] nums, int k, int multiplier) {4    if (multiplier == 1) {5      return nums;6    }7    PriorityQueue<long[]> pq =8        new PriorityQueue<>((a, b)->a[0] == b[0] ? Long.compare(a[1], b[1])9                                                 : Long.compare(a[0], b[0]));10    int n = nums.length;11    int m = Arrays.stream(nums).max().getAsInt();12    for (int i = 0; i < n; ++i) {13      pq.offer(new long[]{nums[i], i});14    }15    for (; k > 0 && pq.peek()[0] < m; --k) {16      long[] p = pq.poll();17      p[0] *= multiplier;18      pq.offer(p);19    }20    final int mod = (int)1 e9 + 7;21    for (int i = 0; i < n; ++i) {22      long[] p = pq.poll();23      long x = p[0];24      int j = (int)p[1];25      nums[j] = (int)((x % mod) *26                      qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);27    }28    return nums;29  }30private31  int qpow(long a, long n, long mod) {32    long ans = 1 % mod;33    for (; n > 0; n >>= 1) {34      if ((n & 1) == 1) {35        ans = ans * a % mod;36      }37      a = a * a % mod;38    }39    return (int)ans;40  }41}

1class Solution {2public:3  vector<int> getFinalState(vector<int> &nums, int k, int multiplier) {4    if (multiplier == 1) {5      return nums;6    }7    using ll = long long;8    using pli = pair<ll, int>;9    auto cmp = [](const pli &a, const pli &b) {10      if (a.first == b.first) {11        return a.second > b.second;12      }13      return a.first > b.first;14    };15    priority_queue<pli, vector<pli>, decltype(cmp)> pq(cmp);16    int n = nums.size();17    int m = *max_element(nums.begin(), nums.end());18    for (int i = 0; i < n; ++i) {19      pq.emplace(nums[i], i);20    }21    while (k > 0 && pq.top().first < m) {22      auto p = pq.top();23      pq.pop();24      p.first *= multiplier;25      pq.emplace(p);26      --k;27    }28    auto qpow = [&](ll a, ll n, ll mod) {29      ll ans = 1 % mod;30      a = a % mod;31      while (n > 0) {32        if (n & 1) {33          ans = ans * a % mod;34        }35        a = a * a % mod;36        n >>= 1;37      }38      return ans;39    };40    const int mod = 1e9 + 7;41    for (int i = 0; i < n; ++i) {42      auto p = pq.top();43      pq.pop();44      long long x = p.first;45      int j = p.second;46      nums[j] = static_cast<int>(47          (x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);48    }49    return nums;50  }51};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int[] getFinalState(int[] nums, int k, int multiplier) {4    if (multiplier == 1) {5      return nums;6    }7    PriorityQueue<long[]> pq =8        new PriorityQueue<>((a, b)->a[0] == b[0] ? Long.compare(a[1], b[1])9                                                 : Long.compare(a[0], b[0]));10    int n = nums.length;11    int m = Arrays.stream(nums).max().getAsInt();12    for (int i = 0; i < n; ++i) {13      pq.offer(new long[]{nums[i], i});14    }15    for (; k > 0 && pq.peek()[0] < m; --k) {16      long[] p = pq.poll();17      p[0] *= multiplier;18      pq.offer(p);19    }20    final int mod = (int)1 e9 + 7;21    for (int i = 0; i < n; ++i) {22      long[] p = pq.poll();23      long x = p[0];24      int j = (int)p[1];25      nums[j] = (int)((x % mod) *26                      qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);27    }28    return nums;29  }30private31  int qpow(long a, long n, long mod) {32    long ans = 1 % mod;33    for (; n > 0; n >>= 1) {34      if ((n & 1) == 1) {35        ans = ans * a % mod;36      }37      a = a * a % mod;38    }39    return (int)ans;40  }41}

1class Solution {2public:3  vector<int> getFinalState(vector<int> &nums, int k, int multiplier) {4    if (multiplier == 1) {5      return nums;6    }7    using ll = long long;8    using pli = pair<ll, int>;9    auto cmp = [](const pli &a, const pli &b) {10      if (a.first == b.first) {11        return a.second > b.second;12      }13      return a.first > b.first;14    };15    priority_queue<pli, vector<pli>, decltype(cmp)> pq(cmp);16    int n = nums.size();17    int m = *max_element(nums.begin(), nums.end());18    for (int i = 0; i < n; ++i) {19      pq.emplace(nums[i], i);20    }21    while (k > 0 && pq.top().first < m) {22      auto p = pq.top();23      pq.pop();24      p.first *= multiplier;25      pq.emplace(p);26      --k;27    }28    auto qpow = [&](ll a, ll n, ll mod) {29      ll ans = 1 % mod;30      a = a % mod;31      while (n > 0) {32        if (n & 1) {33          ans = ans * a % mod;34        }35        a = a * a % mod;36        n >>= 1;37      }38      return ans;39    };40    const int mod = 1e9 + 7;41    for (int i = 0; i < n; ++i) {42      auto p = pq.top();43      pq.pop();44      long long x = p.first;45      int j = p.second;46      nums[j] = static_cast<int>(47          (x % mod) * qpow(multiplier, k / n + (i < k % n ? 1 : 0), mod) % mod);48    }49    return nums;50  }51};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.