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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countInversions ( int arr [ ] , int n ) { vector < int > v ; for ( int i = 1 ; i <= n ; i ++ ) { v . push_back ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { auto itr = lower_bound ( v . begin ( ) , v . end ( ) , arr [ i ] ) ; ans += itr - v . begin ( ) ; v . erase ( itr ) ; } cout << ans ; return 0 ; } int main ( ) { int arr [ ] = { 2 , 3 , 1 , 5 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countInversions ( arr , n ) ; return 0 ; }