Cuente las inversiones en una secuencia generada al agregar una array dada K veces

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 ² )
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++ 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 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.

# 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# 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.

<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 ² )
Espacio Auxiliar: O(1)