Description
Solutions
Get Minimum Operations to Sort Array
🔥 FULLTIME🤘 INTERN

You are given an unsorted array of length n. You can do the following operation any number of time:

  • You can select any element of the array, arr[i] and break it into two parts a and b where a+b = arr[i] and a, b > 0.

We have to find the minimum number of this operation to sort the given array in ascending order.

Example 1: 

Input:  arr = [3, 4, 3], n = 3
Output: 2 
Explanation:

      

        We can take arr[1] and break it into 2 and 2 thus making the array, arr = [3, 2, 2, 3].
        Next we can take arr[0] and break it into 1 and 2, thus making the array, arr = [1, 2, 2, 2, 3].
        After these 2 operations the array is now sorted. Thus the answer is 2.
Constraints:
    • 1 <= n <= 10^5
    • 1 <= arr[i] <= 10^9
Thumbnail 0
Testcase
Result
Case 1

input:

output: