Número mínimo de operaciones requeridas para hacer una permutación de los primeros N números naturales iguales

Dada una array A[] de tamaño N , que contiene una permutación de los primeros N números naturales y un entero K , la tarea es encontrar el número mínimo de operaciones requeridas para igualar todos los elementos de la array seleccionando K ( 1 < K ≤ N ) elementos de array consecutivos y reemplazándolos con el mínimo de los elementos seleccionados.

Ejemplos:

Entrada: A[] = {4, 2, 1, 5, 3}, K = 3, N = 5
Salida: 2
Explicación: Seleccione elementos consecutivos del índice 1 a 3 y reemplácelos con el mínimo de {4, 2, 1 }. Por lo tanto, A[] se convierte en {1, 1, 1, 5, 3}.
Seleccione elementos consecutivos del índice del 3 al 5 y reemplácelos con un mínimo de {1, 5, 3}. Por lo tanto, A se convierte en {1, 1, 1, 1, 1}.
Por lo tanto, el número total de operaciones requeridas son 2.

Entrada: A[] = {3, 6, 2, 1, 4, 5}, K = 2, N=6
Salida: 5
Explicación: Seleccione elementos consecutivos del índice 4 a 5 y reemplácelos con el mínimo de {1, 4 } es 1. Por lo tanto, A[] se convierte en {3, 6, 2, 1, 1, 5}
Seleccione elementos consecutivos del índice 5 a 6 y reemplácelos con el mínimo de {1, 5} es 1. Por lo tanto, A[] se convierte en {3, 6, 2, 1, 1, 1}
Seleccione elementos consecutivos del índice 3 a 4 y reemplácelos con el mínimo de {2, 1} es 1. Por lo tanto, A[] se convierte en {3, 6, 1, 1 , 1, 1}
Seleccione elementos consecutivos del índice 2 a 3 y reemplácelos con el mínimo de {6, 1} es 1. Por lo tanto, A[] se convierte en {3, 1, 1, 1, 1, 1}
Seleccione elementos consecutivos de índice 1 a 2 y reemplazar con el mínimo de {3, 1} es 1. Por lo tanto, A[] se convierte en {1, 1, 1, 1, 1, 1}
Por lo tanto, el número total de operaciones son 5.

Enfoque: La idea se basa en las siguientes observaciones:

• La permutación no importa. Es lo mismo que poner el mínimo al principio.
• El número óptimo de operaciones requeridas se puede calcular comenzando con el índice mínimo y avanzando por K .

El problema se puede resolver imaginando que el mínimo está al principio del arreglo y de ahí en adelante seleccionando K elementos consecutivos. Siga los pasos a continuación para resolver el problema:

• Inicialice las variables i y cuente como 0 , para iterar y contar el número mínimo de operaciones respectivamente.
• Bucle mientras i es menor que N – 1 porque cuando i llega a N – 1 , todos los elementos se han igualado. En cada iteración actual, realice los siguientes pasos:
  • Incrementa el conteo en 1 .
  • Incremente i por K-1 porque el elemento actualizado más a la derecha se usaría nuevamente para el siguiente segmento.
• Imprime el valor de count como resultado.

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 find the minimum
// number of operations required
// to make all array elements equal
int MinimumOperations(int A[],
                      int N, int K)
{
    // Store the count of
    // operations required
    int Count = 0;
 
    int i = 0;
 
    while (i < N - 1) {
 
        // Increment by K - 1, as the last
        // element will be used again for
        // the next K consecutive elements
        i = i + K - 1;
 
        // Increment count by 1
        Count++;
    }
 
    // Return the result
    return Count;
}
 
// Driver Code
int main()
{
    // Given Input
    int A[] = { 5, 4, 3, 1, 2 };
    int K = 3;
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << MinimumOperations(A, N, K) << endl;
 
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
       
      // Function to find the minimum
    // number of operations required
    // to make all array elements equal
 
    static int MinimumOperations(int[] A, int N, int K)
    {
        // Store the count of
        // operations required
        int Count = 0;
 
        int i = 0;
 
        while (i < N - 1) {
 
            // Increment by K - 1, as the last
            // element will be used again for
            // the next K consecutive elements
            i = i + K - 1;
 
            // Increment count by 1
            Count++;
        }
 
        // Return the result
        return Count;
    }
 
    // Driver Code
    public static void main (String[] args) {
        // Given Input
        int[] A = { 5, 4, 3, 1, 2 };
        int K = 3;
        int N = A.length;
 
        System.out.println(MinimumOperations(A, N, K));
    }
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
 
# Function to find the minimum
# number of operations required
# to make all array elements equal
def MinimumOperations(A, N, K):
     
    # Store the count of
    # operations required
    Count = 0
 
    i = 0
 
    while (i < N - 1):
 
        # Increment by K - 1, as the last
        # element will be used again for
        # the next K consecutive elements
        i = i + K - 1
 
        # Increment count by 1
        Count += 1
 
    # Return the result
    return Count
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    A = [ 5, 4, 3, 1, 2 ]
    K = 3
    N = len(A)
 
    print (MinimumOperations(A, N, K))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG {
    // Function to find the minimum
    // number of operations required
    // to make all array elements equal
 
    static int MinimumOperations(int[] A, int N, int K)
    {
        // Store the count of
        // operations required
        int Count = 0;
 
        int i = 0;
 
        while (i < N - 1) {
 
            // Increment by K - 1, as the last
            // element will be used again for
            // the next K consecutive elements
            i = i + K - 1;
 
            // Increment count by 1
            Count++;
        }
 
        // Return the result
        return Count;
    }
 
    // Driver Code
    public static void Main()
    {
        // Given Input
        int[] A = { 5, 4, 3, 1, 2 };
        int K = 3;
        int N = A.Length;
 
        Console.WriteLine(MinimumOperations(A, N, K));
    }
}
 
// This code is contributed by ukasp.

<script>
 
        // JavaScript program for the above approach
 
        // Function to find the minimum
        // number of operations required
        // to make all array elements equal
 
        function MinimumOperations(A, N, K) {
            // Store the count of
            // operations required
            let Count = 0;
 
            let i = 0;
 
            while (i < N - 1) {
 
                // Increment by K - 1, as the last
                // element will be used again for
                // the next K consecutive elements
                i = i + K - 1;
 
                // Increment count by 1
                Count++;
            }
 
            // Return the result
            return Count;
        }
 
        // Driver Code
        // Given Input
        let A = [5, 4, 3, 1, 2];
        let K = 3;
        let N = A.length;
 
        document.write(MinimumOperations(A, N, K));
 
        // This code is contributed by Hritik
         
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)