Problem Statement

Given a 0-indexed integer array nums, return the minimum number of operations to make an array that is sorted in a non-decreasing order.

In a single operation, you can pick any element of the array and replace it with any two elements that sum to it.

• For example, consider nums = [4,3,5]. In one operation, you can replace nums[0] with 1 and 3 and convert nums to [1,3,3,5].

Examples

• Example 1:

  • Input: nums = [4, 3, 2]
  • Expected Output: 4
  • Justification: Replace 4 with two 2s (1 operation), resulting in [2, 2, 3, 2]. Then, to maintain non-decreasing order, replace the first two elements with 1 and 1 (2 operations), and the 3 with 1 and 2 (1 operation), totaling 4 operations.

• Example 2:

  • Input: nums = [3, 4, 5, 6, 7]
  • Expected Output: 0
  • Justification: The array is already in non-decreasing order, so no operations are needed.

• Example 3:

  • Input: nums = [6, 3, 9, 7, 4]
  • Expected Output: 4
  • Justification:
    • Replace 6 with 3 and 3 (1 operation).
    • Replace 9 with 3 and 6, and then replace 6 with 3 and 3 (2 operations).
    • Replace 7 with 3 and 4 (1 operation).
    • Total 4 operations.

Try it yourself

Try solving this question here: