Minimum Replacements To Sort Array
MediumGreedy · Paypal
You are given an array of positive integers nums. In one operation you may pick any element and replace it, in its position, with two positive integers that add up to it. For example, [4, 7, 2] can become [4, 3, 4, 2] by splitting the 7 into 3 and 4. The array grows by one element with each operation.
Return the minimum number of operations needed to make the array non-decreasing (each element is less than or equal to the one after it).
Example 1
- Input:
- nums = [5, 8, 3]
- Output:
- 4
- Explanation
- Work from the right. The
8must become pieces of at most 3, so split it into2, 3, 3(2 operations). Now the5must be at most 2, so split it into1, 2, 2(2 operations). The array[1, 2, 2, 2, 3, 3, 3]is sorted after 4 operations.
Example 2
- Input:
- nums = [10, 1]
- Output:
- 9
- Explanation
- The final
1cannot be split into positive parts, so the10has to become ten 1s, which takes 9 operations.
Example 3
- Input:
- nums = [2, 3, 3]
- Output:
- 0
- Explanation
- The array is already non-decreasing, so no operations are needed.
Constraints
- 1 ≤
nums.length≤ 105 - 1 ≤
nums[i]≤ 109