Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2366.html

2366. Minimum Replacements to Sort the Array

  • Difficulty: Hard.
  • Related Topics: Array, Math, Greedy.
  • Similar Questions: Minimum Operations to Make the Array Increasing.

Problem

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

Solution

  • class Solution {
    public long minimumReplacement(int[] nums) {
        int limit = nums[nums.length - 1];
        long ans = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            int replacements = nums[i] / limit - 1;
            if (nums[i] % limit != 0) {
                replacements++;
            }
            ans += replacements;
            limit = nums[i] / (replacements + 1);
        }
        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:
    def minimumReplacement(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        mi = nums[-1]
        for i in range(n - 2, -1, -1):
            v = nums[i]
            if v <= mi:
                mi = v
                continue
            k = (v + mi - 1) // mi
            ans += k - 1
            mi = v // k
        return ans

############

# 2366. Minimum Replacements to Sort the Array
# https://leetcode.com/problems/minimum-replacements-to-sort-the-array

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        prev = nums[-1]
        
        for i in range(n - 2, -1, -1):
            if nums[i] > prev:
                sections = ceil(nums[i] / prev)
                res += sections - 1
                prev = nums[i] // sections
            
            else:
                prev = nums[i]
            
        return res


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

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions