Minimum Replacements to Sort the Array
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 replacenums[1]with2and4and convertnumsto[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
2Replacing 9 with 3 and 6, then replacing 6 with 3 and 3, makes the array non-decreasing in 2 operations.
Example 2
Input
nums = [1,2,3,4,5]Output
0The array is already in non-decreasing order, so no operations are needed.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9