Dada una array arr[] , la tarea es agregar la array dada exactamente K – 1 veces hasta su final e imprimir el número total de inversiones en la array resultante.
Ejemplos:
Entrada: arr[]= {2, 1, 3}, K = 3
Salida: 12
Explicación:
Agregar 2 copias de la array arr[] modifica arr[] a {2, 1, 3, 2, 1, 3, 2, 1, 3}
Los pares (arr[i], arr[j]), donde i < j y arr[i] > arr[j] son (2, 1), (2, 1), (2, 1) , (3, 2), (3, 1), (3, 2), (3, 1), (2, 1), (2, 1), (3, 2), (3, 1), ( 2, 1)
Por lo tanto, el número total de inversiones es 12.Entrada: arr[]= {6, 2}, K = 2
Salida: 3
Explicación:
Agregar 2 copias de la array arr[] = {6, 2, 6, 2}
Los pares (arr[i], arr[j] ), donde i < j y arr[i] > arr[j] son (6, 2), (6, 2), (6, 2)
Por lo tanto, el número total de inversiones es 3.
Enfoque ingenuo: el enfoque más simple es almacenar K copias de la array dada en un vector y luego encontrar el recuento de inversiones del vector resultante.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(K * N)
Enfoque eficiente: la idea para resolver este problema es encontrar primero el número total de inversiones en la array dada, digamos inv . Luego, cuente pares de elementos distintos en una sola copia, digamos X . Ahora, calcule el número total de inversiones después de agregar K copias de la array mediante la ecuación:
(inv*K + ((K*(K-1))/2)*X).
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sanachaitali30 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA