Count Inversions of size three in a give array - GeeksforGeeks

Count Inversions of size three in a give array - GeeksforGeeks

Count Inversions of size three in a give array Given an array arr[] of size n. Three elements arr[i], arr[j] and arr[k] form an inversion of size 3 if a[i] > a[j] >a[k] and i < j < k. Find total number of inversions of size 3. Example: Input: {8, 4, 2, 1} Output: 4 The four inversions are (8,4,2), (8,4,1), (4,2,1) and (8,2,1). Input: {9, 6, 4, 5, 8} Output: 2 The two inversions are {9, 6, 4} and {9, 6, 5} Simple approach :- Loop for all possible value of i, j and k and check for the condition a[i] > a[j] > a[k] and i < j < k. // A Simple C++ O(n^3) program to count inversions of size 3 #include using namespace std; // Returns counts of inversions of size three int getInvCount(int arr[],int n) { int invcount = 0; // Initialize result for (int i=0; iarr[j]) { for (int k=j+1; karr[k]) invcount++; } } } } return invcount; } // Driver program to test above function int main() { int arr[] = {8,

Read full article from Count Inversions of size three in a give array - GeeksforGeeks