Count inversions in a sequence generated by appending given array K times | C ++ program for the above approach ; Function to count the number of inversions in K copies of given array ; Stores count of inversions in the given array ; Stores the count of pairs of distinct array elements ; Traverse the array ; Generate each pair ; Check for each pair , if the condition is satisfied or not ; If pairs consist of distinct elements ; Count inversiosn in the sequence ; Print the answer ; Driver Code ; Given array ; Given K ; Size of the array
#include <bits/stdc++.h> NEW_LINE using namespace std ; void totalInversions ( int arr [ ] , int K , int N ) { int inv = 0 ; int X = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( arr [ i ] > arr [ j ] and i < j ) inv ++ ; if ( arr [ i ] > arr [ j ] ) X ++ ; } } int totalInv = X * K * ( K - 1 ) / 2 + inv * K ; cout << totalInv << endl ; } int main ( ) { int arr [ ] = { 2 , 1 , 3 } ; int K = 3 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; totalInversions ( arr , K , N ) ; }