Count inversions in a permutation of first N natural numbers | C # program for the above approach ; Function to count number of inversions in a permutation of first N natural numbers ; Store array elements in sorted order ; Store the count of inversions ; Traverse the array ; Store the index of first occurrence of arr [ i ] in vector V ; Add count of smaller elements than current element ; Erase current element from vector and go to next index ; Print the result ; Driver code ; Given Input ; Function Call
using System ; using System . Collections . Generic ; class GFG { static void countInversions ( int [ ] arr , int n ) { List < int > v = new List < int > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { v . Add ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int itr = v . IndexOf ( arr [ i ] ) ; ans += itr ; v . RemoveAt ( itr ) ; } Console . WriteLine ( ans ) ; } public static void Main ( string [ ] args ) { int [ ] arr = { 2 , 3 , 1 , 5 , 4 } ; int n = arr . Length ; countInversions ( arr , n ) ; } }