Scale Engineer

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
ArrayHeap (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 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

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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem