Count inversions in a permutation of first N natural numbers

Count inversions in a permutation of first N natural numbers

Given an array, arr[] of size N denoting a permutation of numbers from 1 to N, the task is to count the number of inversions in the array.
Note: Two array elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Examples:

Input: arr[] = {2, 3, 1, 5, 4}
Output: 3
Explanation: Given array has 3 inversions: (2, 1), (3, 1), (5, 4).

Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has 2 inversions: (3, 1), (3, 2).

Different methods to solve inversion count has been discussed in the following articles:  

Approach: This problem can be solved by using binary search. Follow the steps below to solve the problem:

• Store the numbers in the range [1, N] in increasing order in a vector, V.
• Initialize a variable, ans as 0 to store the number of inversions in the array, arr[].
• Iterate in the range [0, N-1] using the variable i
• Print the value of ans as the result.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h> 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; }

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets