Minimum Moves to Sort Array

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.

Constraints

N/A

Example 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}

Example 2

Input:

arr = [3, 2, 4]

Output:

1

Explanation: Split 3 into two parts (1, 2). Array becomes (1, 2, 2, 4).

Example 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.