**Problem**

Given an array of integers, count the number of inversions present in it. An inversion is such that arr[i] > arr[j] and i<j.

**Sample Input**

[3, 4, 1]

**Sample Output**

Inversion count is 2

**Approach 1**

Traverse through the array, and for every index, find the number of smaller elements on its right side. This can be done using nested loops. Sum up the counts for all indexes in the array.

The time complexity of this approach is O(N2).

**C Programming**

#include <stdio.h> #include <stdlib.h> int solve(int arr[], int n) { // nested loops int ans = 0; for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if (arr[i] > arr[j]) //if found the required condition ans++; return ans; } int main() { int arr[] = {3, 4, 1 }; int n = sizeof(arr) / sizeof(arr[0]); printf(" Inversion count is %d ",solve(arr, n)); return 0; }

**Output**

Inversion count is 2

**Python Programming**

def solve(arr, n): ans = 0 # use two nested loops for i in range(n): for j in range(i + 1, n): if (arr[i] > arr[j]): #if condition is satisfied ans += 1 return ans arr = [3, 4, 1] n = len(arr) print("Inversion count is", solve(arr, n))

**Output**

Inversion count is 2

**Approach 2**

We can solve this problem using sets in C++. The sets in C++ implement Self-Balancing BST. Following is an algorithm to implement this approach

Create an empty set and insert the first element of the array into the set. Also initialize *ans* variable to 0 which stores inversion count.

Iterate from 1 to *n*-1 and

- Insert
*arr*[i] into the set. - Find the upper bound of
*arr*[i] in the set. - Find the distance of the upper bound with the last element of the set and add this distance to
*ans.*

The worst case time complexity of this approach can go upto O(N2) but still the computation time is relatively less than the brute force method.

**C++ Programming**

#include<bits/stdc++.h> using namespace std; int solve(int arr[],int n) { multiset<int> set1; set1.insert(arr[0]); int ans = 0; multiset<int>::iterator itset1; for (int i=1; i<n; i++) { // insert element into the set set1.insert(arr[i]); // find the upper bound of the element itset1 = set1.upper_bound(arr[i]); // add distance to the answer ans += distance(itset1, set1.end()); } return ans; } int main() { int arr[] = {3, 4, 1}; int n = sizeof(arr)/sizeof(int); cout << "Inversion count is " << solve(arr,n); return 0; }

**Output**

Inversion count is 2

**People are also reading:**