Dados cuatro números N , L , R y S , la tarea es encontrar una permutación de los primeros N números naturales (indexación basada en 1) que tengan la suma como S del índice L a R . Si hay varias permutaciones, imprima cualquiera de ellas. De lo contrario, imprima -1 .
Ejemplos:
Entrada: N = 6, L = 3, R = 5, S = 8
Salida: 3 4 5 2 1 6
Explicación: La permutación de salida tiene 5 en el índice L y 1 en el índice R. La suma de los números de L a R es 8(5+2+1).Entrada: N = 4, L = 2, R = 3, S = 2
Salida: -1
Explicación: No existe ninguna permutación en la que la suma de los números del índice L a R sea S.
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso, que se basa en la observación de que se deben elegir X números de una permutación de los primeros N números naturales , por lo que para hacer la suma como S , la suma mínima y máxima de X números son minSum y maxSum respectivamente, entonces:
X = R – L + 1
suma mínima = X(X + 1)/2
suma máxima = X(2*N + 1 – X)/2
Por lo tanto, si la suma dada S se encuentra en el rango [minSum, maxSum] , entonces existe una permutación tal que la suma de todos los números de L a R es S. De lo contrario, no existe tal permutación. Siga los pasos a continuación para resolver el problema:
- Defina una función posible (int x, int S, int N) y realice las siguientes tareas:
- Inicialice la variable minSum como x*(x + 1)/2 y maxSum como (x * ((2*N) – x + 1))/2 .
- Si S es menor que minSum o S es mayor que maxSum , devuelve false . De lo contrario, devuelve verdadero .
- Inicialice la variable, digamos x como (R – L + 1) .
- Si el valor devuelto por la función posible (x, S, N) devuelve falso, imprima -1 y regrese de la función .
- De lo contrario, inicialice un vector v[] para almacenar los números presentes dentro del segmento dado.
- Iterar sobre el rango [N, 1] usando la variable i y realizar las siguientes tareas:
- Si S – i es mayor que igual a 0 y la función posible (x – 1, S – i, i – 1) devuelve verdadero , entonces establezca S como (S – i) disminuya el valor de x en 1 y aumente el valor de i en el vector v[] .
- Si S es igual a 0 , salga del bucle .
- Si S no es igual a 0 , imprima -1 y regrese.
- Inicialice un vector, digamos v1[] para almacenar los números que no están presentes dentro del segmento dado.
- Itere sobre el rango [1, N] usando la variable i e inicialice un iterador de vector y compruebe si el elemento i está presente en el vector v[] usando find() o no. Si no está presente, introdúzcalo en el vector v1 .
- Inicialice las variables j y f como 0 para imprimir los resultados.
- Itere sobre el rango [1, L) usando la variable i e imprima el valor de v1[j] , y aumente el valor de j en 1 .
- Itere sobre el rango [L, R] usando la variable i e imprima el valor de v[f] , y aumente el valor de f en 1 .
- Itere sobre el rango [R+1, N] usando la variable i e imprima el valor de v1[j] , y aumente el valor de j en 1 .
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 check if sum is possible
// with remaining numbers
bool possible(int x, int S, int N)
{
// Stores the minimum sum possible with
// x numbers
int minSum = (x * (x + 1)) / 2;
// Stores the maximum sum possible with
// x numbers
int maxSum = (x * ((2 * N) - x + 1)) / 2;
// If S lies in the range
// [minSum, maxSum]
if (S < minSum || S > maxSum) {
return false;
}
return true;
}
// Function to find the resultant
// permutation
void findPermutation(int N, int L,
int R, int S)
{
// Stores the count of numbers
// in the given segment
int x = R - L + 1;
// If the sum is not possible
// with numbers in the segment
if (!possible(x, S, N)) {
// Output -1
cout << -1;
return;
}
else {
// Stores the numbers present
// within the given segment
vector<int> v;
// Iterate over the numbers from
// 1 to N
for (int i = N; i >= 1; --i) {
// If (S-i) is a positive non-zero
// sum and if it is possible to
// obtain (S-i) remaining numbers
if ((S - i) >= 0
&& possible(x - 1, S - i,
i - 1)) {
// Update sum S
S = S - i;
// Update required numbers
// in the segment
x--;
// Push i in vector v
v.push_back(i);
}
// If sum has been obtained
if (S == 0) {
// Break from the loop
break;
}
}
// If sum is not obtained
if (S != 0) {
// Output -1
cout << -1;
return;
}
// Stores the numbers which are
// not present in given segment
vector<int> v1;
// Loop to check the numbers not
// present in the segment
for (int i = 1; i <= N; ++i) {
// Pointer to check if i is
// present in vector v or not
vector<int>::iterator it
= find(v.begin(), v.end(), i);
// If i is not present in v
if (it == v.end()) {
// Push i in vector v1
v1.push_back(i);
}
}
// Point to the first elements
// of v1 and v respectively
int j = 0, f = 0;
// Print the required permutation
for (int i = 1; i < L; ++i) {
cout << v1[j] << " ";
j++;
}
for (int i = L; i <= R; ++i) {
cout << v[f] << " ";
f++;
}
for (int i = R + 1; i <= N; ++i) {
cout << v1[j] << " ";
j++;
}
}
return;
}
// Driver Code
int main()
{
int N = 6, L = 3, R = 5, S = 8;
findPermutation(N, L, R, S);
return 0;
}
Java
import java.util.ArrayList;
// Java program for the above approach
class GFG{
// Function to check if sum is possible
// with remaining numbers
public static boolean possible(int x, int S, int N)
{
// Stores the minimum sum possible with
// x numbers
int minSum = (x * (x + 1)) / 2;
// Stores the maximum sum possible with
// x numbers
int maxSum = (x * ((2 * N) - x + 1)) / 2;
// If S lies in the range
// [minSum, maxSum]
if (S < minSum || S > maxSum) {
return false;
}
return true;
}
// Function to find the resultant
// permutation
public static void findPermutation(int N, int L,
int R, int S)
{
// Stores the count of numbers
// in the given segment
int x = R - L + 1;
// If the sum is not possible
// with numbers in the segment
if (!possible(x, S, N)) {
// Output -1
System.out.print(-1);
return;
}
else {
// Stores the numbers present
// within the given segment
ArrayList<Integer> v = new ArrayList<>();
// Iterate over the numbers from
// 1 to N
for (int i = N; i >= 1; --i) {
// If (S-i) is a positive non-zero
// sum and if it is possible to
// obtain (S-i) remaining numbers
if ((S - i) >= 0
&& possible(x - 1, S - i,
i - 1)) {
// Update sum S
S = S - i;
// Update required numbers
// in the segment
x--;
// Push i in vector v
v.add(i);
}
// If sum has been obtained
if (S == 0) {
// Break from the loop
break;
}
}
// If sum is not obtained
if (S != 0) {
// Output -1
System.out.print(-1);
return;
}
// Stores the numbers which are
// not present in given segment
ArrayList<Integer> v1 = new ArrayList<Integer>();
// Loop to check the numbers not
// present in the segment
for (int i = 1; i <= N; ++i) {
// Pointer to check if i is
// present in vector v or not
boolean it = v.contains(i);
// If i is not present in v
if (!it) {
// Push i in vector v1
v1.add(i);
}
}
// Point to the first elements
// of v1 and v respectively
int j = 0, f = 0;
// Print the required permutation
for (int i = 1; i < L; ++i) {
System.out.print(v1.get(j) + " ");
j++;
}
for (int i = L; i <= R; ++i) {
System.out.print(v.get(f) + " ");
f++;
}
for (int i = R + 1; i <= N; ++i) {
System.out.print(v1.get(j) + " ");
j++;
}
}
return;
}
// Driver Code
public static void main(String args[])
{
int N = 6, L = 3, R = 5, S = 8;
findPermutation(N, L, R, S);
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python program for the above approach
# Function to check if sum is possible
# with remaining numbers
def possible(x, S, N):
# Stores the minimum sum possible with
# x numbers
minSum = (x * (x + 1)) // 2
# Stores the maximum sum possible with
# x numbers
maxSum = (x * ((2 * N) - x + 1)) // 2
# If S lies in the range
# [minSum, maxSum]
if (S < minSum or S > maxSum):
return False
return True
# Function to find the resultant
# permutation
def findPermutation(N, L, R, S):
# Stores the count of numbers
# in the given segment
x = R - L + 1
# If the sum is not possible
# with numbers in the segment
if (not possible(x, S, N)):
# Output -1
print("-1")
return
else:
# Stores the numbers present
# within the given segment
v = []
# Iterate over the numbers from
# 1 to N
for i in range(N, 0, -1):
# If (S-i) is a positive non-zero
# sum and if it is possible to
# obtain (S-i) remaining numbers
if ((S - i) >= 0 and possible(x - 1, S - i, i - 1)):
# Update sum S
S = S - i
# Update required numbers
# in the segment
x -= 1
# Push i in vector v
v.append(i)
# If sum has been obtained
if (S == 0):
# Break from the loop
break
# If sum is not obtained
if (S != 0):
# Output -1
print(-1)
return
# Stores the numbers which are
# not present in given segment
v1 = []
# Loop to check the numbers not
# present in the segment
for i in range(1, N+1):
# Pointer to check if i is
# present in vector v or not
it = i in v
# If i is not present in v
if (not it):
# Push i in vector v1
v1.append(i)
# Point to the first elements
# of v1 and v respectively
j = 0
f = 0
# Print the required permutation
for i in range(1, L):
print(v1[j], end = " ")
j += 1
for i in range(L, R + 1):
print(v[f], end = " ")
f += 1
for i in range(R + 1, N + 1):
print(v1[j], end = " ")
j += 1
return
# Driver Code
if __name__ == "__main__":
N = 6
L = 3
R = 5
S = 8
findPermutation(N, L, R, S)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check if sum is possible
// with remaining numbers
public static bool possible(int x, int S, int N)
{
// Stores the minimum sum possible with
// x numbers
int minSum = (x * (x + 1)) / 2;
// Stores the maximum sum possible with
// x numbers
int maxSum = (x * ((2 * N) - x + 1)) / 2;
// If S lies in the range
// [minSum, maxSum]
if (S < minSum || S > maxSum) {
return false;
}
return true;
}
// Function to find the resultant
// permutation
public static void findPermutation(int N, int L, int R,
int S)
{
// Stores the count of numbers
// in the given segment
int x = R - L + 1;
// If the sum is not possible
// with numbers in the segment
if (!possible(x, S, N)) {
// Output -1
Console.WriteLine(-1);
return;
}
else {
// Stores the numbers present
// within the given segment
List<int> v = new List<int>();
// Iterate over the numbers from
// 1 to N
for (int i = N; i >= 1; --i) {
// If (S-i) is a positive non-zero
// sum and if it is possible to
// obtain (S-i) remaining numbers
if ((S - i) >= 0
&& possible(x - 1, S - i, i - 1)) {
// Update sum S
S = S - i;
// Update required numbers
// in the segment
x--;
// Push i in vector v
v.Add(i);
}
// If sum has been obtained
if (S == 0) {
// Break from the loop
break;
}
}
// If sum is not obtained
if (S != 0) {
// Output -1
Console.WriteLine(-1);
return;
}
// Stores the numbers which are
// not present in given segment
List<int> v1 = new List<int>();
// Loop to check the numbers not
// present in the segment
for (int i = 1; i <= N; ++i) {
// Pointer to check if i is
// present in vector v or not
bool it = v.Contains(i);
// If i is not present in v
if (!it) {
// Push i in vector v1
v1.Add(i);
}
}
// Point to the first elements
// of v1 and v respectively
int j = 0, f = 0;
// Print the required permutation
for (int i = 1; i < L; ++i) {
Console.Write(v1[j] + " ");
j++;
}
for (int i = L; i <= R; ++i) {
Console.Write(v[f] + " ");
f++;
}
for (int i = R + 1; i <= N; ++i) {
Console.Write(v1[j] + " ");
j++;
}
}
return;
}
// Driver Code
public static void Main()
{
int N = 6, L = 3, R = 5, S = 8;
findPermutation(N, L, R, S);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to check if sum is possible
// with remaining numbers
function possible(x, S, N) {
// Stores the minimum sum possible with
// x numbers
let minSum = (x * (x + 1)) / 2;
// Stores the maximum sum possible with
// x numbers
let maxSum = (x * (2 * N - x + 1)) / 2;
// If S lies in the range
// [minSum, maxSum]
if (S < minSum || S > maxSum) {
return false;
}
return true;
}
// Function to find the resultant
// permutation
function findPermutation(N, L, R, S) {
// Stores the count of numbers
// in the given segment
let x = R - L + 1;
// If the sum is not possible
// with numbers in the segment
if (!possible(x, S, N)) {
// Output -1
document.write(-1);
return;
} else {
// Stores the numbers present
// within the given segment
let v = [];
// Iterate over the numbers from
// 1 to N
for (let i = N; i >= 1; --i) {
// If (S-i) is a positive non-zero
// sum and if it is possible to
// obtain (S-i) remaining numbers
if (S - i >= 0 && possible(x - 1, S - i, i - 1)) {
// Update sum S
S = S - i;
// Update required numbers
// in the segment
x--;
// Push i in vector v
v.push(i);
}
// If sum has been obtained
if (S == 0) {
// Break from the loop
break;
}
}
// If sum is not obtained
if (S != 0) {
// Output -1
document.write(-1);
return;
}
// Stores the numbers which are
// not present in given segment
let v1 = [];
// Loop to check the numbers not
// present in the segment
for (let i = 1; i <= N; ++i) {
// Pointer to check if i is
// present in vector v or not
it = v.includes(i);
// If i is not present in v
if (!it) {
// Push i in vector v1
v1.push(i);
}
}
// Point to the first elements
// of v1 and v respectively
let j = 0,
f = 0;
// Print the required permutation
for (let i = 1; i < L; ++i) {
document.write(v1[j] + " ");
j++;
}
for (let i = L; i <= R; ++i) {
document.write(v[f] + " ");
f++;
}
for (let i = R + 1; i <= N; ++i) {
document.write(v1[j] + " ");
j++;
}
}
return;
}
// Driver Code
let N = 6,
L = 3,
R = 5,
S = 8;
findPermutation(N, L, R, S);
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
3 4 5 2 1 6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA