Problem Brief
Minimum Moves to Sort Array
FULLTIMEINTERNOA
Given an array arr[] of N integers, the task is to find the minimum number of moves to sort the array in non-decreasing order by splitting any array element into two parts such that the sum of the parts is the same as that element.
1Example 1
Input
arr = [3, 4, 2]
Output
2
Explanation
The moves are:
- Split 4 into two parts (2, 2). Array becomes
arr[] = {3, 2, 2, 2} - Split 3 into two parts (1, 2). Array becomes
arr[] = {1, 2, 2, 2, 2}
2Example 2
Input
arr = [3, 2, 4]
Output
1
Explanation
Split 3 into two parts (1, 2). Array becomes (1, 2, 2, 4).
3Example 3
Input
arr = [5, 6, 5, 7, 9]
Output
2
Explanation
At Index = 0, 5 breaks into 2, 3 so array becomes (2, 3, 6, 5, 7, 9).
At Index = 1, 6 breaks into 3, 3 so array becomes (2, 3, 3, 3, 5, 7, 9).
Now the array is sorted (2, 3, 3, 3, 5, 7, 9), so the count is 2. Hence the function returns 2.