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
- 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 numbers int 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 Code int 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 approach import java.util.Vector; class GFG{ // Function to count number of inversions in // a permutation of first N natural numbers static 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 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 abhinavjain194 |
Python3
# Python3 program for the above approach from bisect import bisect_left # Function to count number of inversions in # a permutation of first N natural numbers def 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 Code if __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 approach using 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 numbers function 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 Input var arr = [ 2, 3, 1, 5, 4 ]; var n = arr.length; // Function Call countInversions(arr, n); // This code is contributed by bgangwar59 </script> |
Output:
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Contact Us