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>
Producción
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