Question

2366. Minimum Replacements to Sort the Array

中文文档

Description

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

• For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return _the minimum number of operations to make an array that is sorted in non-decreasing order_.

 

Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0. 

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solutions

Solution 1: Greedy Approach

We observe that to make the array $nums$ non-decreasing or monotonically increasing, the elements towards the end of the array should be as large as possible. Therefore, it is unnecessary to replace the last element $nums[n-1]$ of the array $nums$ with multiple smaller numbers.

In other words, we can traverse the array $nums$ from the end to the beginning, maintaining the current maximum value $mx$, initially $mx = nums[n-1]$.

• If the current element $nums[i] \leq mx$, there is no need to replace $nums[i]$. We simply update $mx = nums[i]$.
• Otherwise, we need to replace $nums[i]$ with multiple numbers that sum to $nums[i]$. The maximum of these numbers is $mx$, and the total number of replacements is $k=\left \lceil \frac{nums[i]}{mx} \right \rceil$. Therefore, we need to perform $k-1$ operations, which are added to the answer. Among these $k$ numbers, the smallest number is $\left \lfloor \frac{nums[i]}{k} \right \rfloor$. Therefore, we update $mx = \left \lfloor \frac{nums[i]}{k} \right \rfloor$.

After the traversal, we return the total number of operations.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def minimumReplacement(self, nums: List[int]) -> int:
    ans = 0
    n = len(nums)
    mx = nums[-1]
    for i in range(n - 2, -1, -1):
      if nums[i] <= mx:
        mx = nums[i]
        continue
      k = (nums[i] + mx - 1) // mx
      ans += k - 1
      mx = nums[i] // k
    return ans

class Solution {
  public long minimumReplacement(int[] nums) {
    long ans = 0;
    int n = nums.length;
    int mx = nums[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] <= mx) {
        mx = nums[i];
        continue;
      }
      int k = (nums[i] + mx - 1) / mx;
      ans += k - 1;
      mx = nums[i] / k;
    }
    return ans;
  }
}

class Solution {
public:
  long long minimumReplacement(vector<int>& nums) {
    long long ans = 0;
    int n = nums.size();
    int mx = nums[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] <= mx) {
        mx = nums[i];
        continue;
      }
      int k = (nums[i] + mx - 1) / mx;
      ans += k - 1;
      mx = nums[i] / k;
    }
    return ans;
  }
};

func minimumReplacement(nums []int) (ans int64) {
  n := len(nums)
  mx := nums[n-1]
  for i := n - 2; i >= 0; i-- {
    if nums[i] <= mx {
      mx = nums[i]
      continue
    }
    k := (nums[i] + mx - 1) / mx
    ans += int64(k - 1)
    mx = nums[i] / k
  }
  return
}

function minimumReplacement(nums: number[]): number {
  const n = nums.length;
  let mx = nums[n - 1];
  let ans = 0;
  for (let i = n - 2; i >= 0; --i) {
    if (nums[i] <= mx) {
      mx = nums[i];
      continue;
    }
    const k = Math.ceil(nums[i] / mx);
    ans += k - 1;
    mx = Math.floor(nums[i] / k);
  }
  return ans;
}

impl Solution {
  #[allow(dead_code)]
  pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
    if nums.len() == 1 {
      return 0;
    }

    let n = nums.len();
    let mut max = *nums.last().unwrap();
    let mut ret = 0;

    for i in (0..=n - 2).rev() {
      if nums[i] <= max {
        max = nums[i];
        continue;
      }
      // Otherwise make the substitution
      let k = (nums[i] + max - 1) / max;
      ret += (k - 1) as i64;
      // Update the max value, which should be the minimum among the substitution
      max = nums[i] / k;
    }

    ret
  }
}