Dada una array arr[], que consiste en N enteros positivos distintos y un entero K, la tarea es encontrar la permutación lexicográficamente más pequeña de la array , tal que la suma de los elementos de cualquier prefijo de la array de salida no sea igual a la K . Si no existe tal permutación, imprima » -1 «. De lo contrario, imprima la array de salida.
Ejemplos:
Entrada: arr[] = {2, 6, 4, 5, 3, 1}, K = 15
Salida: 1 2 3 4 6 5
Explicación:
La permutación lexicográficamente más pequeña de la array dada es, {1, 2, 3, 4, 6, 5} sin prefijo de suma igual a 15.Entrada: arr[]={3, 1, 4, 6}, K = 12
Salida: 1 3 4 6
Explicación:
La permutación lexicográficamente más pequeña de la array dada es {1, 3, 4, 6} sin prefijo de suma igual a 12.
Enfoque: el problema se puede resolver ordenando primero la array en orden ascendente y luego intercambiando el último elemento del prefijo cuya suma es igual a K , con el siguiente elemento. Siga los pasos a continuación para resolver este problema:
- Si la suma de la array es igual a K , imprima » -1 «, ya que será imposible encontrar cualquier permutación de la array que satisfaga las condiciones.
- Ordene la array en orden ascendente.
- Inicialice una variable, diga preSum como 0 para almacenar la suma de un prefijo.
- Iterar sobre el rango [0, N-2] usando la variable i y realizar los siguientes pasos:
- Incremente presuSuma por arr[i] .
- Si preSum es igual a K, entonces intercambie arr[i] y arr[i+1] y luego rompa .
- Finalmente, después de completar los pasos anteriores, imprima los elementos de la array, arr[] .
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 output array // satisfying given conditions void findpermutation(int arr[], int N, int K) { int sum = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { sum = sum + arr[i]; } // If sum is equal to K if (sum == K) { cout << -1 << endl; } else { // Sort array in ascending order sort(arr, arr + N); // Stores the sum of a prefix int preSum = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Update the preSum preSum = preSum + arr[i]; // If preSum is equal to K if (preSum == K) { // Swap swap(arr[i], arr[i + 1]); break; } } // Print the array arr[] for (int i = 0; i < N; i++) { cout << arr[i] << " "; } cout << endl; } } // Driver code int main() { int arr[] = { 2, 6, 4, 5, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 15; findpermutation(arr, N, K); }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the output array // satisfying given conditions static void findpermutation(int arr[], int N, int K) { int sum = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { sum = sum + arr[i]; } // If sum is equal to K if (sum == K) { System.out.println(-1); } else { // Sort array in ascending order Arrays.sort(arr); // Stores the sum of a prefix int preSum = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Update the preSum preSum = preSum + arr[i]; // If preSum is equal to K if (preSum == K) { // Swap swap(arr, i, i + 1); break; } } // Print the array arr[] for(int i = 0; i < N; i++) { System.out.print(arr[i] + " "); } System.out.println( ); } } static int[] swap(int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void main(String[] args) { int arr[] = { 2, 6, 4, 5, 3, 1 }; int N = arr.length; int K = 15; findpermutation(arr, N, K); } } // This code is contributed by shivanisinghss2110
Python3
# Python3 program for the above approach # Function to find the output array # satisfying given conditions def findpermutation(arr, N, K): sum = 0 # Traverse the array arr[] for i in range(0, N): sum = sum + arr[i] # If sum is equal to K if (sum == K): print("-1") else: # Sort array in ascending order arr.sort() # Stores the sum of a prefix preSum = 0 # Traverse the array arr[] for i in range(0, N): # Update the preSum preSum = preSum + arr[i] # If preSum is equal to K if (preSum == K): # Swap temp = arr[i] arr[i] = arr[i + 1] arr[i + 1] = temp # Print the array arr[] for i in range(0, N): print(arr[i], end = " ") # Driver code arr = [ 2, 6, 4, 5, 3, 1 ] N = len(arr) K = 15 findpermutation(arr, N, K) # This code is contributed by amreshkumar3
C#
// C# program for the above approach using System; class GFG{ // Function to find the output array // satisfying given conditions static void findpermutation(int []arr, int N, int K) { int sum = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { sum = sum + arr[i]; } // If sum is equal to K if (sum == K) { Console.WriteLine(-1); } else { // Sort array in ascending order Array.Sort(arr); // Stores the sum of a prefix int preSum = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Update the preSum preSum = preSum + arr[i]; // If preSum is equal to K if (preSum == K) { // Swap swap(arr, i, i + 1); break; } } // Print the array arr[] for(int i = 0; i < N; i++) { Console.WriteLine(arr[i] + " "); } Console.WriteLine( ); } } static int[] swap(int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code static void Main() { int []arr= { 2, 6, 4, 5, 3, 1 }; int N = arr.Length; int K = 15; findpermutation(arr, N, K); } } // This code is contributed by SoumikMondal
Javascript
<script> // JavaScript program for the above approach // Function to find the output array // satisfying given conditions function findpermutation(arr, N, K) { var sum = 0; var i; // Traverse the array arr[] for (i = 0; i < N; i++) { sum = sum + arr[i]; } // If sum is equal to K if (sum == K) { document.write(-1); } else { // Sort array in ascending order arr = arr.sort(function(a, b) { return a - b; }); // Stores the sum of a prefix var preSum = 0; // Traverse the array arr[] for (i = 0; i < N; i++) { // Update the preSum preSum = preSum + arr[i]; // If preSum is equal to K if (preSum == K) { // Swap var temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; break; } } // Print the array arr[] for (i = 0; i < N; i++) { document.write(arr[i] + " "); } document.write("<br>") } } // Driver code arr = [2, 6, 4, 5, 3, 1]; N = arr.length; K = 15; findpermutation(arr, N, K); </script>
1 2 3 4 6 5
Complejidad temporal: O(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