Dada una array arr de longitud N , la tarea es contar el número mínimo de operaciones para convertir la secuencia dada en una permutación de los primeros N números naturales (1, 2, …., N) . En cada operación, incrementa o decrementa un elemento en uno.
Ejemplos:
Entrada: arr[] = {4, 1, 3, 6, 5}
Salida: 4
Aplicar la operación de decremento cuatro veces en 6
Entrada: arr[] = {0, 2, 3, 4, 1, 6, 8, 9}
Salida : 7
Enfoque : un enfoque eficiente es ordenar la array dada y, para cada elemento, encontrar la diferencia entre arr[i] e i (indexación basada en 1). Encuentre la suma de todas esas diferencias, y estos serán los pasos mínimos requeridos.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find minimum number of steps to // convert a given sequence into a permutation #include <bits/stdc++.h> using namespace std; // Function to find minimum number of steps to // convert a given sequence into a permutation int get_permutation(int arr[], int n) { // Sort the given array sort(arr, arr + n); // To store the required minimum // number of operations int result = 0; // Find the operations on each step for (int i = 0; i < n; i++) { result += abs(arr[i] - (i + 1)); } // Return the answer return result; } // Driver code int main() { int arr[] = { 0, 2, 3, 4, 1, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << get_permutation(arr, n); return 0; }
Java
// Java program to find minimum number of steps to // convert a given sequence into a permutation import java.util.*; class GFG{ // Function to find minimum number of steps to // convert a given sequence into a permutation static int get_permutation(int arr[], int n) { // Sort the given array Arrays.sort(arr); // To store the required minimum // number of operations int result = 0; // Find the operations on each step for (int i = 0; i < n; i++) { result += Math.abs(arr[i] - (i + 1)); } // Return the answer return result; } // Driver code public static void main(String[] args) { int arr[] = { 0, 2, 3, 4, 1, 6, 8, 9 }; int n = arr.length; // Function call System.out.print(get_permutation(arr, n)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to find minimum number of steps to # convert a given sequence into a permutation # Function to find minimum number of steps to # convert a given sequence into a permutation def get_permutation(arr, n): # Sort the given array arr = sorted(arr) # To store the required minimum # number of operations result = 0 # Find the operations on each step for i in range(n): result += abs(arr[i] - (i + 1)) # Return the answer return result # Driver code if __name__ == '__main__': arr=[0, 2, 3, 4, 1, 6, 8, 9] n = len(arr) # Function call print(get_permutation(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# program to find minimum number of steps to // convert a given sequence into a permutation using System; class GFG{ // Function to find minimum number of steps to // convert a given sequence into a permutation static int get_permutation(int []arr, int n) { // Sort the given array Array.Sort(arr); // To store the required minimum // number of operations int result = 0; // Find the operations on each step for (int i = 0; i < n; i++) { result += Math.Abs(arr[i] - (i + 1)); } // Return the answer return result; } // Driver Code public static void Main() { int []arr = { 0, 2, 3, 4, 1, 6, 8, 9 }; int n = arr.Length; // Function call Console.Write(get_permutation(arr, n)); } } // This code is contributed by shivanisinghss2110
Javascript
<script> // javascript program to find minimum number of steps to // convert a given sequence into a permutation // Function to find minimum number of steps to // convert a given sequence into a permutation function get_permutation(arr , n) { // Sort the given array arr.sort(); // To store the required minimum // number of operations var result = 0; // Find the operations on each step for (i = 0; i < n; i++) { result += Math.abs(arr[i] - (i + 1)); } // Return the answer return result; } // Driver code var arr = [ 0, 2, 3, 4, 1, 6, 8, 9 ]; var n = arr.length; // Function call document.write(get_permutation(arr, n)); // This code is contributed by Amit Katiyar </script>
7
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA