- Arrays, Greedy, Mathematical, Sorting, subarray

Split given Array in minimum number of subarrays such that rearranging the order of subarrays sorts the array

Given an array arr[] consisting of N integers, the task is to find the minimum number of splitting of array elements into subarrays such that rearranging the order of subarrays sorts the given array.Examples:Input: arr[] = {6, 3, 4, 2, 1}Output: 4Explanation:The given array can be divided into 4 subarrays as {6}, {3, 4}, {2}, {1} and these subarrays can be rearranged as {1}, {2}, {3, 4}, {6}. The resulting array will be {1, 2, 3, 4, 6} which is sorted. So, the minimum subarrays the given array can be divided to sort the array is 4.Input: arr[] = {1, -4, 0, -2}Output: 4Approach: The given problem can be solved by maintaining a sorted version of the array arr[] and grouping together all integers in the original array which appear in the same sequence as in the sorted array. Below are the steps:Maintain a vector of pair V that stores the value of the current element and the index of the current element of the array arr[] for all elements in the given array.Sort the vector V.Initialize a variable, say cnt as 1 that stores the minimum number of subarrays required.Traverse the vector V for i in the range [1, N – 1] and perform the following steps:If the index of the ithelement in the original array is (1 + index of (i – 1)th element) in the original array, then the two can be grouped together in the same subarray.Otherwise, the two elements need to be in separate subarrays and increment the value of cnt by 1.After completing the above steps, print the value of cnt as the resultant possible breaking of subarrays.Below is the implementation of the above approach:C++  #include   #include using namespace std;  int numberOfSubarrays(int arr[], int n){            int cnt = 1;              vector v(n);          for (int i = 0; i < n; i++) {        v[i].first = arr[i];        v[i].second = i;    }          sort(v.begin(), v.end());          for (int i = 1; i < n; i++) {                          if (v[i].second == v[i - 1].second + 1) {            continue;        }        else {            cnt++;        }    }          return cnt;}  int main(){    int arr[] = { 6, 3, 4, 2, 1 };    int N = sizeof(arr) / sizeof(arr[0]);    cout