Problem Brief

Get Minimum Operations to Sort Array

FULLTIMEINTERNOA

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.

1Example 1

Input

arr = [3, 4, 3], n = 3

Output

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

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
1 <= arr[i] <= 10^9

Draft autosaves locally

public int getMinimumOperationsToSortArray(int[] arr, int n) {
  // write your code here
}

Input

arr

[3, 4, 3]

Output