Count inversions in a sequence generated by appending given array K times
Given an array arr[], the task is to append the given array exactly K – 1 times to its end and print the total number of inversions in the resulting array.
Examples:
Input: arr[]= {2, 1, 3}, K = 3
Output: 12
Explanation:
Appending 2 copies of array arr[] modifies arr[] to {2, 1, 3, 2, 1, 3, 2, 1, 3}
The pairs (arr[i], arr[j]), where i < j and arr[i] > arr[j] are (2, 1), (2, 1), (2, 1), (3, 2), (3, 1), (3, 2), (3, 1), (2, 1), (2, 1), (3, 2), (3, 1), (2, 1)
Therefore, the total number of inversions are 12.Input: arr[]= {6, 2}, K = 2
Output: 3
Explanation:
Appending 2 copies of array arr[] = {6, 2, 6, 2}
The pairs (arr[i], arr[j]), where i < j and arr[i] > arr[j] are (6, 2), (6, 2), (6, 2)
Therefore, the total number of inversions are 3.
Naive Approach: The simplest approach is to store K copies of the given array in a vector and then, find the count of inversions of the resulting vector.
Time Complexity: O(N2)
Auxiliary Space: O(K * N)
Efficient Approach: The idea to solve this problem is to first find the total number of inversions in the given array, say inv. Then, count pairs of distinct elements in a single copy, say X. Now, calculate the total number of inversions after appending K copies of the array by the equation:
(inv*K + ((K*(K-1))/2)*X).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of // inversions in K copies of given array void totalInversions( int arr[], int K, int N) { // Stores count of inversions // in the given array int inv = 0; // Stores the count of pairs // of distinct array elements int X = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Generate each pair for ( int j = 0; j < N; j++) { // Check for each pair, if the // condition is satisfied or not if (arr[i] > arr[j] and i < j) inv++; // If pairs consist of // distinct elements if (arr[i] > arr[j]) X++; } } // Count inversion in the sequence int totalInv = X * K * (K - 1) / 2 + inv * K; // Print the answer cout << totalInv << endl; } // Driver Code int main() { // Given array int arr[] = { 2, 1, 3 }; // Given K int K = 3; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); totalInversions(arr, K, N); } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to count the number of // inversions in K copies of given array static void totalInversions( int arr[], int K, int N) { // Stores count of inversions // in the given array int inv = 0 ; // Stores the count of pairs // of distinct array elements int X = 0 ; int i, j; // Traverse the array for (i = 0 ; i < N; i++) { // Generate each pair for (j = 0 ; j < N; j++) { // Check for each pair, if the // condition is satisfied or not if (arr[i] > arr[j] && i < j) inv++; // If pairs consist of // distinct elements if (arr[i] > arr[j]) X++; } } // Count inversion in the sequence int totalInv = X * K * (K - 1 ) / 2 + inv * K; // Print the answer System.out.println(totalInv); } // Driver Code public static void main(String args[]) { // Given array int arr[] = { 2 , 1 , 3 }; // Given K int K = 3 ; // Size of the array int N = arr.length; totalInversions(arr, K, N); } } // This code is contributed by bgangwar59. |
Python3
# Python program of the above approach # Function to count the number of # inversions in K copies of given array def totalInversions(arr, K, N) : # Stores count of inversions # in the given array inv = 0 # Stores the count of pairs # of distinct array elements X = 0 # Traverse the array for i in range (N): # Generate each pair for j in range (N): # Check for each pair, if the # condition is satisfied or not if (arr[i] > arr[j] and i < j) : inv + = 1 # If pairs consist of # distinct elements if (arr[i] > arr[j]) : X + = 1 # Count inversion in the sequence totalInv = X * K * (K - 1 ) / / 2 + inv * K # Print the answer print (totalInv) # Driver Code # Given array arr = [ 2 , 1 , 3 ] # Given K K = 3 # Size of the array N = len (arr) totalInversions(arr, K, N) # This code is contributed by susmitakundugoaldanga |
C#
// C# program to implement // the above approach using System; class GFG { // Function to count the number of // inversions in K copies of given array static void totalInversions( int []arr, int K, int N) { // Stores count of inversions // in the given array int inv = 0; // Stores the count of pairs // of distinct array elements int X = 0; int i, j; // Traverse the array for (i = 0; i < N; i++) { // Generate each pair for (j = 0; j < N; j++) { // Check for each pair, if the // condition is satisfied or not if (arr[i] > arr[j] && i < j) inv++; // If pairs consist of // distinct elements if (arr[i] > arr[j]) X++; } } // Count inversion in the sequence int totalInv = X * K * (K - 1) / 2 + inv * K; // Print the answer Console.WriteLine(totalInv); } // Driver Code public static void Main() { // Given array int []arr = { 2, 1, 3 }; // Given K int K = 3; // Size of the array int N = arr.Length; totalInversions(arr, K, N); } } // This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript program for // the above approach // Function to count the number of // inversions in K copies of given array function totalInversions(arr, K, N) { // Stores count of inversions // in the given array let inv = 0; // Stores the count of pairs // of distinct array elements let X = 0; let i, j; // Traverse the array for (i = 0; i < N; i++) { // Generate each pair for (j = 0; j < N; j++) { // Check for each pair, if the // condition is satisfied or not if (arr[i] > arr[j] && i < j) inv++; // If pairs consist of // distinct elements if (arr[i] > arr[j]) X++; } } // Count inversion in the sequence let totalInv = X * K * (K - 1) / 2 + inv * K; // Print the answer document.write(totalInv); } // Driver Code // Given array let arr = [ 2, 1, 3 ]; // Given K let K = 3; // Size of the array let N = arr.length; totalInversions(arr, K, N); </script> |
12
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us