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
- Store the index of occurrence of arr[i] in vector V in a variable index.
- Add the count of numbers having positions less than the index that are present in the vector, V since they are smaller than the current element and thus form inversions.
- Remove the element at position index from the vector, V.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count number of inversions in// a permutation of first N natural numbersint countInversions(int arr[], int n){ vector<int> v; // Store array elements in sorted order for (int i = 1; i <= n; i++) { v.push_back(i); } // Store the count of inversions int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // Store the index of first // occurrence of arr[i] in vector V auto itr = lower_bound( v.begin(), v.end(), arr[i]); // Add count of smaller elements // than current element ans += itr - v.begin(); // Erase current element from // vector and go to next index v.erase(itr); } // Print the result cout << ans; return 0;}// Driver Codeint main(){ // Given Input int arr[] = { 2, 3, 1, 5, 4 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call countInversions(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.Vector;class GFG{// Function to count number of inversions in// a permutation of first N natural numbersstatic void countInversions(int arr[], int n){ Vector<Integer> v = new Vector<>(); // Store array elements in sorted order for(int i = 1; i <= n; i++) { v.add(i); } // Store the count of inversions int ans = 0; // Traverse the array for(int i = 0; i < n; i++) { // Store the index of first // occurrence of arr[i] in vector V int itr = v.indexOf(arr[i]); // Add count of smaller elements // than current element ans += itr; // Erase current element from // vector and go to next index v.remove(itr); } // Print the result System.out.println(ans);}// Driver codepublic static void main(String[] args){ // Given Input int arr[] = { 2, 3, 1, 5, 4 }; int n = arr.length; // Function Call countInversions(arr, n);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approachfrom bisect import bisect_left# Function to count number of inversions in# a permutation of first N natural numbersdef countInversions(arr, n): v = [] # Store array elements in sorted order for i in range(1, n + 1, 1): v.append(i) # Store the count of inversions ans = 0 # Traverse the array for i in range(n): # Store the index of first # occurrence of arr[i] in vector V itr = bisect_left(v, arr[i]) # Add count of smaller elements # than current element ans += itr # Erase current element from # vector and go to next index v = v[:itr] + v[itr + 1 :] # Print the result print(ans)# Driver Codeif __name__ == '__main__': # Given Input arr = [ 2, 3, 1, 5, 4 ] n = len(arr) # Function Call countInversions(arr, n) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to count number of inversions in // a permutation of first N natural numbers static void countInversions(int[] arr, int n) { List<int> v = new List<int>(); // Store array elements in sorted order for (int i = 1; i <= n; i++) { v.Add(i); } // Store the count of inversions int ans = 0; // Traverse the array for(int i =0 ;i <n;i ++){ // Store the index of first // occurrence of arr[i] in vector V int itr = v.IndexOf(arr[i]); // Add count of smaller elements // than current element ans += itr; // Erase current element from // vector and go to next index v.RemoveAt(itr); } // Print the result Console.WriteLine(ans); } // Driver code public static void Main(string[] args) { // Given Input int[] arr = { 2, 3, 1, 5, 4 }; int n = arr.Length; // Function Call countInversions(arr, n); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to count number of inversions in// a permutation of first N natural numbersfunction countInversions(arr, n){ var v = []; var i; // Store array elements in sorted order for(i = 1; i <= n; i++) { v.push(i); } // Store the count of inversions var ans = 0; // Traverse the array for(i = 0; i < n; i++) { // Store the index of first // occurrence of arr[i] in vector V var index = v.indexOf(arr[i]); // Add count of smaller elements // than current element ans += index; // Erase current element from // vector and go to next index v.splice(index, 1); } // Print the result document.write(ans);}// Driver code// Given Inputvar arr = [ 2, 3, 1, 5, 4 ];var n = arr.length;// Function CallcountInversions(arr, n);// This code is contributed by bgangwar59</script> |
Output:
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
