Dada una array A[] de tamaño N , la tarea es encontrar la suma mínima de números necesarios para agregar a los elementos de la array para convertir la array en una permutación de 1 a N. Si la array no se puede convertir a la permutación deseada, imprima -1 .
Ejemplos:
Entrada: A[] = {1, 1, 1, 1, 1}
Salida: 10
Explicación: Incrementar A[1] en 1, A[2] en 2, A[3] en 3, A[4] en 4 , por lo que A[] se convierte en {1, 2, 3, 4, 5}.
Adiciones mínimas requeridas = 1 + 2 + 3 + 4 = 10Entrada: A[] = {2, 2, 3}
Salida: -1
Enfoque: La idea es usar sorting . Siga estos pasos para resolver este problema:
- Inicialice una variable y almacene el resultado requerido.
- Ordene la array dada A[] en orden creciente .
- Atraviesa el arreglo , A[] usando la variable i
- Si el valor de A[i] > i+1 , actualice ans a -1 y salga del bucle .
- De lo contrario, incremente ans por la diferencia de i+1 y A[i] .
- Imprime el valor de ans como resultado.
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 find the minimum additions required // to convert the array into a permutation of 1 to N int minimumAdditions(int a[], int n) { // Sort the array in increasing order sort(a, a + n); int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // If a[i] > i + 1, then return -1 if ((i + 1) - a[i] < 0) { return -1; } if ((i + 1) - a[i] > 0) { // Update answer ans += (i + 1 - a[i]); } } // Return the required result return ans; } // Driver Code int main() { // Given Input int A[] = { 1, 1, 1, 1, 1 }; int n = sizeof(A) / sizeof(A[0]); // Function Call cout << minimumAdditions(A, n); return 0; }
Java
// Java program for the above approach import java.util.Arrays; public class GFG { // Function to find the minimum additions required // to convert the array into a permutation of 1 to N static int minimumAdditions(int a[], int n) { // Sort the array in increasing order Arrays.sort(a); int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // If a[i] > i + 1, then return -1 if ((i + 1) - a[i] < 0) { return -1; } if ((i + 1) - a[i] > 0) { // Update answer ans += (i + 1 - a[i]); } } // Return the required result return ans; } // Driver code public static void main(String[] args) { // Given Input int A[] = { 1, 1, 1, 1, 1 }; int n = A.length; // Function Call System.out.println(minimumAdditions(A, n)); } } // This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to find the minimum additions # required to convert the array into a # permutation of 1 to N def minimumAdditions(a, n): # Sort the array in increasing order a = sorted(a) ans = 0 # Traverse the array for i in range(n): # If a[i] > i + 1, then return -1 if ((i + 1) - a[i] < 0): return -1 if ((i + 1) - a[i] > 0): # Update answer ans += (i + 1 - a[i]) # Return the required result return ans # Driver Code if __name__ == '__main__': # Given Input A = [ 1, 1, 1, 1, 1 ] n = len(A) # Function Call print(minimumAdditions(A, n)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum additions // required to convert the array into a // permutation of 1 to N static int minimumAdditions(int []a, int n) { // Sort the array in increasing order Array.Sort(a); int ans = 0; // Traverse the array for(int i = 0; i < n; i++) { // If a[i] > i + 1, then return -1 if ((i + 1) - a[i] < 0) { return -1; } if ((i + 1) - a[i] > 0) { // Update answer ans += (i + 1 - a[i]); } } // Return the required result return ans; } // Driver code static void Main() { // Given Input int[] A = { 1, 1, 1, 1, 1 }; int n = A.Length; // Function Call Console.Write(minimumAdditions(A, n)); } } // This code is contributed by SoumikMondal
Javascript
<script> // Javascript program for the above approach // Function to find the minimum additions required // to convert the array into a permutation of 1 to N function minimumAdditions(a, n) { // Sort the array in increasing order a.sort(function(a, b){return a-b;}); let ans = 0; // Traverse the array for (let i = 0; i < n; i++) { // If a[i] > i + 1, then return -1 if ((i + 1) - a[i] < 0) { return -1; } if ((i + 1) - a[i] > 0) { // Update answer ans += (i + 1 - a[i]); } } // Return the required result return ans; } // Driver code // Given Input let A = [ 1, 1, 1, 1, 1 ]; let n = A.length; // Function Call document.write(minimumAdditions(A, n)); // This code is contributed by unknown2108 </script>
10
Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA