Minimum swaps to reach permuted array with at most 2 positions left swaps allowed | C ++ program to find minimum number of swaps to reach a permutation with at most 2 left swaps allowed for every element ; This funt merges two sorted arrays and returns inversion count in the arrays . ; i is index for left subarray ; j is index for right subarray ; k is index for resultant merged subarray ; Copy the remaining elements of left subarray ( if there are any ) to temp ; Copy the remaining elements of right subarray ( if there are any ) to temp ; Copy back the merged elements to original array ; An auxiliary recursive function that sorts the input array and returns the number of inversions in the array . ; Divide the array into two parts and call _mergeSortAndCountInv ( ) for each of the parts ; Inversion count will be sum of inversions in left - part , right - part and number of inversions in merging ; Merge the two parts ; This function sorts the input array and returns the number of inversions in the array ; method returns minimum number of swaps to reach permuted array ' arr ' ; loop over all elements to check Invalid permutation condition ; if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning - 1 ; If permuted array is not Invalid , then number of Inversion in array will be our final answer ; Driver code to test above methods ; change below example
#include <bits/stdc++.h> NEW_LINE using namespace std ; int merge ( int arr [ ] , int temp [ ] , int left , int mid , int right ) { int inv_count = 0 ; int i = left ; int j = mid ; int k = left ; while ( ( i <= mid - 1 ) && ( j <= right ) ) { if ( arr [ i ] <= arr [ j ] ) temp [ k ++ ] = arr [ i ++ ] ; else { temp [ k ++ ] = arr [ j ++ ] ; inv_count = inv_count + ( mid - i ) ; } } while ( i <= mid - 1 ) temp [ k ++ ] = arr [ i ++ ] ; while ( j <= right ) temp [ k ++ ] = arr [ j ++ ] ; for ( i = left ; i <= right ; i ++ ) arr [ i ] = temp [ i ] ; return inv_count ; } int _mergeSort ( int arr [ ] , int temp [ ] , int left , int right ) { int mid , inv_count = 0 ; if ( right > left ) { mid = ( right + left ) / 2 ; inv_count = _mergeSort ( arr , temp , left , mid ) ; inv_count += _mergeSort ( arr , temp , mid + 1 , right ) ; inv_count += merge ( arr , temp , left , mid + 1 , right ) ; } return inv_count ; } int mergeSort ( int arr [ ] , int array_size ) { int * temp = ( int * ) malloc ( sizeof ( int ) * array_size ) ; return _mergeSort ( arr , temp , 0 , array_size - 1 ) ; } int minSwapToReachArr ( int arr [ ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { if ( ( arr [ i ] - 1 ) - i > 2 ) return -1 ; } int numOfInversion = mergeSort ( arr , N ) ; return numOfInversion ; } int main ( ) { int arr [ ] = { 1 , 2 , 5 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int res = minSwapToReachArr ( arr , N ) ; if ( res == -1 ) cout << " Not ▁ Possible STRNEWLINE " ; else cout << res << endl ; return 0 ; }