Minimum Replacements to Sort the Array - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2366. Minimum Replacements to Sort the Array
Hard
50 Points
Array
Math
Greedy
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.
Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Examples
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
2366. Minimum Replacements to Sort the Array
Hard
50 Points
Array
Math
Greedy
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.
Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Examples
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.