Minimum De | CPP for counting minimum de - arrangements present in an array . ; function to count Dearrangement ; create a copy of original array ; sort the array ; traverse sorted array for counting mismatches ; reverse the sorted array ; traverse reverse sorted array for counting mismatches ; return minimum mismatch count ; driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countDe ( int arr [ ] , int n ) { vector < int > v ( arr , arr + n ) ; sort ( arr , arr + n ) ; int count1 = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( arr [ i ] != v [ i ] ) count1 ++ ; reverse ( arr , arr + n ) ; int count2 = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( arr [ i ] != v [ i ] ) count2 ++ ; return ( min ( count1 , count2 ) ) ; } int main ( ) { int arr [ ] = { 5 , 9 , 21 , 17 , 13 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Minimum ▁ Dearrangement ▁ = ▁ " << countDe ( arr , n ) ; return 0 ; }