Dados los números enteros L, R, X e Y tales que (R > L ≥ 1), (X ≥ 0) y (Y ≥ 0). Encuentre la permutación de los números en el rango [L, R] tal que haya exactamente X picos y Y valles presentes en la permutación. Imprima Sí y la permutación si se encuentra la permutación. De lo contrario imprima No.
Nota: en un arreglo arr[] hay un pico en el i-ésimo índice si arr[i-1] < arr[i] > arr[i+1] y un valle en el i-ésimo índice si arr[i-1] > arr[i ] < arr[i+1], donde 0< i < N .
Ejemplos:
Entrada: L = 1, R = 3, X = 1, Y = 0
Salida: Sí, arr[] = { 1, 3, 2 }
Explicación: se requiere 1 pico y no se requiere valle.
Claramente arr[0] < arr[1] > arr[2], arr[1] es el pico.Entrada: L = 4, R = 8, X = 4, Y = 1
Salida: No
Explicación: No existe tal permutación de tamaño 5 con 4 picos y 1 valle.Entrada: L = 3, R = 5, X = 0, Y = 0
Salida: Sí, arr[] = { 3, 4, 5 }
Explicación: se requieren 0 picos y 0 valles.
La array ordenada no tiene pico ni valle.
Enfoque: Puede haber cinco casos siguientes. Siga los enfoques mencionados para cada caso.
Caso-1 (Sin permutación posible): El primer y último elemento de la permutación no contribuye a la cantidad de picos y valles.
- Entonces, si (X + Y) > (R – L – 1) no habrá permutación que satisfaga los números de picos y valles.
- Además, si el valor absoluto de (X – Y) > 1 , no habrá tal permutación, porque hay exactamente 1 valle entre dos picos y viceversa.
Caso-2 (X = 0, Y = 0): Siga los pasos que se mencionan a continuación.
- Cree una array arr[] de tamaño (R – L + 1) y almacene los números en el rango [L, R] en orden ordenado en la array.
- Imprime la array.
Caso-3 (X > Y): Siga los pasos que se mencionan a continuación:
- Cree una array arr[] de tamaño (R – L + 1) que consista en los números en el rango [L, R] en orden ordenado.
- Considere los últimos elementos (X + Y – 1) para asignar picos X y valles Y.
- Iterar desde i = (N – 2) hasta i = (N – (X + Y – 1)) . donde N = (R – L + 1)
- En cada iteración , intercambie arr[i] con arr[i+1] y disminuya i en 2.
- Imprime la array
Caso-4(X <Y): Siga los pasos que se mencionan a continuación:
- Cree una array arr[] de tamaño (R – L + 1) que consista en los números en el rango [L, R] en orden ordenado.
- Considere los primeros elementos (X + Y) para asignar picos X y valles Y.
- Iterar de i = 1 a i = (X+Y) .
- Para cada iteración , intercambie arr[i] con arr[i-1] e incremente i en 2.
- Imprime la array.
Caso-5(X = Y): Siga los pasos que se mencionan a continuación:
- Cree una array arr[] de longitud (R – L + 1) que consista en los números en el rango [L, R] en orden ordenado.
- Considere los primeros elementos (X+Y) para asignar los picos (X-1) y los valles Y.
- Iterar desde i = 1 hasta i = (X+Y).
- Para cada iteración , intercambie arr[i] con arr[i-1] e incremente i en 2.
- Una vez completada la iteración, intercambie los dos últimos elementos de la array para obtener un pico más.
- Imprime la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to build the permutation
void BuildMountainArray(int L, int R, int X, int Y)
{
int N = (R - L + 1);
// Case-1: permutation cannot be built
if (((X + Y) > (N - 2)) || abs(X - Y) > 1) {
cout << "No" << endl;
}
else {
// Vector to store the permutation
vector<int> res(N, 0);
for (int index = 0; index < N;
index++) {
res[index] = L + index;
}
// Case-2: X = 0, Y = 0
if (X == 0 && Y == 0) {
cout << "Yes" << endl;
for (int index = 0; index < N;
index++) {
cout << res[index] << " ";
}
cout << endl;
return;
}
// Case-3: X > Y
// Consider last (X+Y+1) elements
else if (X > Y) {
for (int index = N - 2;
index >= (N - (X + Y + 1));
index -= 2) {
swap(res[index],
res[index + 1]);
}
}
// Case-4: X < Y
// Consider first (X+Y) elements
else if (Y > X) {
for (int index = 1; index <=
(X + Y); index += 2) {
swap(res[index],
res[index - 1]);
}
}
else {
// Case-5: X = Y
// Consider first (X+Y) elements,
// it will give (X-1) peaks
// and Y valleys
for (int index = 1; index <=
(X + Y); index += 2) {
swap(res[index],
res[index - 1]);
}
// Swap last 2 elements,
// to get 1 more peak
swap(res[N - 2], res[N - 1]);
}
// Print the required array
cout << "Yes" << endl;
for (int index = 0; index < N;
index++) {
cout << res[index] << " ";
}
cout << endl;
}
}
// Driver code
int main()
{
// Input
int L = 1, R = 3, X = 1, Y = 0;
// Function call
BuildMountainArray(L, R, X, Y);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG {
// Utility function to build the permutation
static void BuildMountainArray(int L, int R, int X,
int Y)
{
int N = (R - L + 1);
// Case-1: permutation cannot be built
if (((X + Y) > (N - 2)) || Math.abs(X - Y) > 1) {
System.out.println("No");
}
else
{
// Vector to store the permutation
int res[] = new int[N];
for (int index = 0; index < N; index++) {
res[index] = L + index;
}
// Case-2: X = 0, Y = 0
if (X == 0 && Y == 0) {
System.out.println("Yes");
for (int index = 0; index < N; index++) {
System.out.print(res[index] + " ");
}
System.out.println();
return;
}
// Case-3: X > Y
// Consider last (X+Y+1) elements
else if (X > Y) {
for (int index = N - 2;
index >= (N - (X + Y + 1));
index -= 2) {
int temp = res[index];
res[index] = res[index + 1];
res[index + 1] = temp;
}
}
// Case-4: X < Y
// Consider first (X+Y) elements
else if (Y > X) {
for (int index = 1; index <= (X + Y);
index += 2) {
int temp = res[index];
res[index] = res[index - 1];
res[index - 1] = temp;
}
}
else {
// Case-5: X = Y
// Consider first (X+Y) elements,
// it will give (X-1) peaks
// and Y valleys
for (int index = 1; index <= (X + Y);
index += 2) {
int temp = res[index];
res[index] = res[index - 1];
res[index - 1] = temp;
}
// Swap last 2 elements,
// to get 1 more peak
int temp = res[N - 2];
res[N - 2] = res[N - 1];
res[N - 1] = temp;
}
// Print the required array
System.out.println("Yes");
for (int index = 0; index < N; index++) {
System.out.print(res[index] + " ");
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
// Input
int L = 1, R = 3, X = 1, Y = 0;
// Function call
BuildMountainArray(L, R, X, Y);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python code to implement the above approach
import math as Math
# Utility function to build the permutation
def BuildMountainArray(L, R, X, Y):
N = (R - L + 1)
# Case-1: permutation cannot be built
if (((X + Y) > (N - 2)) or Math.fabs(X - Y) > 1):
print("No")
else:
# Vector to store the permutation
res = [0] * N
for index in range(N):
res[index] = L + index
# Case-2: X = 0, Y = 0
if (X == 0 and Y == 0):
print("Yes")
for index in range(N):
print(res[index], end=" ")
print("")
return
# Case-3: X > Y
# Consider last (X+Y+1) elements
elif (X > Y):
for index in range(N - 2, N - (X + Y + 1) - 1, -2):
temp = res[index]
res[index] = res[index + 1]
res[index + 1] = temp
# Case-4: X < Y
# Consider first (X+Y) elements
elif (Y > X):
for index in range(1, X + Y + 1, 2):
temp = res[index]
res[index] = res[index - 1]
res[index - 1] = temp
else:
# Case-5: X = Y
# Consider first (X+Y) elements,
# it will give (X-1) peaks
# and Y valleys
for index in range(1, X + Y + 1, 2):
temp = res[index]
res[index] = res[index - 1]
res[index - 1] = temp
# Swap last 2 elements,
# to get 1 more peak
temp = res[N - 2]
res[N - 2] = res[N - 1]
res[N - 1] = temp
# Print the required array
print("Yes")
for index in range(N):
print(res[index], end=" ")
print("")
# Driver code
# Input
L = 1
R = 3
X = 1
Y = 0
# Function call
BuildMountainArray(L, R, X, Y)
# This code is contributed by Saurabh jaiswal
C#
// C# implementation of above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// Utility function to build the permutation
static void BuildMountainArray(int L, int R, int X,
int Y)
{
int N = (R - L + 1);
// Case-1: permutation cannot be built
if (((X + Y) > (N - 2)) || Math.Abs(X - Y) > 1) {
Console.WriteLine("No");
}
else
{
// Vector to store the permutation
int[] res = new int[N];
for (int index = 0; index < N; index++) {
res[index] = L + index;
}
// Case-2: X = 0, Y = 0
if (X == 0 && Y == 0) {
Console.WriteLine("Yes");
for (int index = 0; index < N; index++) {
Console.Write(res[index] + " ");
}
Console.WriteLine();
return;
}
// Case-3: X > Y
// Consider last (X+Y+1) elements
else if (X > Y) {
for (int index = N - 2;
index >= (N - (X + Y + 1));
index -= 2) {
int temp1 = res[index];
res[index] = res[index + 1];
res[index + 1] = temp1;
}
}
// Case-4: X < Y
// Consider first (X+Y) elements
else if (Y > X) {
for (int index = 1; index <= (X + Y);
index += 2) {
int temp2 = res[index];
res[index] = res[index - 1];
res[index - 1] = temp2;
}
}
else
{
// Case-5: X = Y
// Consider first (X+Y) elements,
// it will give (X-1) peaks
// and Y valleys
for (int index = 1; index <= (X + Y);
index += 2) {
int temp3 = res[index];
res[index] = res[index - 1];
res[index - 1] = temp3;
}
// Swap last 2 elements,
// to get 1 more peak
int temp4 = res[N - 2];
res[N - 2] = res[N - 1];
res[N - 1] = temp4;
}
// Print the required array
Console.WriteLine("Yes");
for (int index = 0; index < N; index++) {
Console.Write(res[index] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
// Input
int L = 1, R = 3, X = 1, Y = 0;
// Function call
BuildMountainArray(L, R, X, Y);
}
}
// This code is contributed sanjoy_62.
Javascript
<script>
// JavaScript code to implement the above approach
// Utility function to build the permutation
const BuildMountainArray = (L, R, X, Y) => {
let N = (R - L + 1);
// Case-1: permutation cannot be built
if (((X + Y) > (N - 2)) || Math.abs(X - Y) > 1) {
document.write("No<br/>");
}
else
{
// Vector to store the permutation
let res = new Array(N).fill(0);
for (let index = 0; index < N;
index++) {
res[index] = L + index;
}
// Case-2: X = 0, Y = 0
if (X == 0 && Y == 0) {
document.write("Yes<br/>");
for (let index = 0; index < N;
index++) {
document.write(`${res[index]} `);
}
document.write("<br/>");
return;
}
// Case-3: X > Y
// Consider last (X+Y+1) elements
else if (X > Y) {
for (let index = N - 2;
index >= (N - (X + Y + 1));
index -= 2) {
let temp = res[index];
res[index] = res[index + 1];
res[index + 1] = temp;
}
}
// Case-4: X < Y
// Consider first (X+Y) elements
else if (Y > X) {
for (let index = 1; index <=
(X + Y); index += 2) {
let temp = res[index];
res[index] = res[index - 1];
res[index - 1] = temp;
}
}
else {
// Case-5: X = Y
// Consider first (X+Y) elements,
// it will give (X-1) peaks
// and Y valleys
for (let index = 1; index <=
(X + Y); index += 2) {
let temp = res[index];
res[index] = res[index - 1];
res[index - 1] = temp;
}
// Swap last 2 elements,
// to get 1 more peak
let temp = res[N - 2];
res[N - 2] = res[N - 1];
res[N - 1] = temp;
}
// Print the required array
document.write("Yes<br/>");
for (let index = 0; index < N;
index++) {
document.write(`${res[index]} `);
}
document.write("<br/>");
}
}
// Driver code
// Input
let L = 1, R = 3, X = 1, Y = 0;
// Function call
BuildMountainArray(L, R, X, Y);
// This code is contributed by rakeshsahni
</script>
Producción
Yes 1 3 2
Complejidad de tiempo: O(N) donde N = (R – L + 1)
Complejidad de espacio: O(1)