Dados los números enteros N , L y R , la tarea es generar una secuencia bitónica de longitud N a partir de los números enteros en el rango [L, R] tal que el primer elemento sea el máximo. Si no es posible crear tal secuencia, imprima «-1» .
Una secuencia bitónica es una secuencia que debe ser estrictamente creciente al principio y luego estrictamente decreciente.
Ejemplos:
Entrada: N = 5, L = 3, R = 10
Salida: 9, 10, 9, 8, 7
Explicación: La secuencia {9, 10, 9, 8, 7} primero es estrictamente creciente y luego estrictamente decreciente.Entrada: N = 5, L = 2, R = 5
Salida: 4, 5, 4, 3, 2
Explicación:
[ La secuencia {4, 5, 4, 3, 2} primero es estrictamente creciente y luego estrictamente decreciente.
Enfoque: La idea es usar un Deque para que se puedan agregar elementos desde el final y el principio. Siga los pasos a continuación para resolver el problema:
- Inicialice un deque para almacenar el elemento de la secuencia bitónica resultante .
- Inicialice una variable i como 0 y comience a agregar elementos en la lista resultante a partir de (R – i) hasta que i sea menor que el mínimo de (R – L + 1) y (N – 1) .
- Después de los pasos anteriores, si el tamaño de la lista resultante es menor que N , agregue elementos de (R – 1) a L desde el comienzo de la lista hasta que el tamaño de la lista resultante no se convierta en N.
- Después de los pasos anteriores, si N es mayor que (R – L)*2 + 1 , entonces no es posible construir tal secuencia y luego imprimir “-1”; de lo contrario, imprimir la secuencia almacenada en deque .
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 construct bitonic
// sequence of length N from
// integers in the range [L, R]
void bitonicSequence(int num, int lower,
int upper)
{
// If sequence is not possible
if (num > (upper - lower) * 2 + 1)
{
cout << -1;
return;
}
// Store the resultant list
deque<int> ans;
deque<int>::iterator j = ans.begin();
for(int i = 0;
i < min(upper - lower + 1, num - 1);
i++)
ans.push_back(upper - i);
// If size of deque < n
for(int i = 0;
i < num - ans.size();
i++)
// Add elements from start
ans.push_front(upper - i - 1);
// Print the stored in the list
cout << '[';
for(j = ans.begin(); j != ans.end(); ++j)
cout << ' ' << *j;
cout << ' ' << ']';
}
// Driver Code
int main()
{
int N = 5, L = 3, R = 10;
// Function Call
bitonicSequence(N, L, R);
return 0;
}
// This code is contributed by jana_sayantan
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to construct bitonic
// sequence of length N from
// integers in the range [L, R]
public static void bitonicSequence(
int num, int lower, int upper)
{
// If sequence is not possible
if (num > (upper - lower) * 2 + 1) {
System.out.println(-1);
return;
}
// Store the resultant list
Deque<Integer> ans
= new ArrayDeque<>();
for (int i = 0;
i < Math.min(upper - lower + 1,
num - 1);
i++)
ans.add(upper - i);
// If size of deque < n
for (int i = 0;
i < num - ans.size(); i++)
// Add elements from start
ans.addFirst(upper - i - 1);
// Print the stored in the list
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int N = 5, L = 3, R = 10;
// Function Call
bitonicSequence(N, L, R);
}
}
Python3
# Python3 program for the above approach from collections import deque # Function to construct bitonic # sequence of length N from # integers in the range [L, R] def bitonicSequence(num, lower, upper): # If sequence is not possible if (num > (upper - lower) * 2 + 1): print(-1) return # Store the resultant list ans = deque() for i in range(min(upper - lower + 1, num - 1)): ans.append(upper - i) # If size of deque < n for i in range(num - len(ans)): # Add elements from start ans.appendleft(upper - i - 1) # Print the stored in the list print(list(ans)) # Driver Code if __name__ == '__main__': N = 5 L = 3 R = 10 # Function Call bitonicSequence(N, L, R) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to construct bitonic
// sequence of length N from
// integers in the range [L, R]
public static void bitonicSequence(int num,
int lower,
int upper)
{
// If sequence is not possible
if (num > (upper - lower) * 2 + 1)
{
Console.WriteLine(-1);
return;
}
// Store the resultant list
List<int> ans = new List<int>();
for(int i = 0;
i < Math.Min(upper - lower + 1,
num - 1); i++)
ans.Add(upper - i);
// If size of deque < n
for(int i = 0;
i < num - ans.Count; i++)
// Add elements from start
ans.Insert(0,upper - i - 1);
// Print the stored in the list
Console.Write("[");
foreach(int x in ans)
Console.Write(x + ", ");
Console.Write("]");
}
// Driver Code
public static void Main(String[] args)
{
int N = 5, L = 3, R = 10;
// Function Call
bitonicSequence(N, L, R);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to construct bitonic
// sequence of length N from
// integers in the range [L, R]
function bitonicSequence(num, lower, upper)
{
// If sequence is not possible
if (num > (upper - lower) * 2 + 1)
{
document.write( -1);
return;
}
// Store the resultant list
var ans = [];
for(var i = 0;
i < Math.min(upper - lower + 1, num - 1);
i++)
ans.push(upper - i);
// If size of deque < n
for(var i = 0;
i < num - ans.length;
i++)
{
// Add elements from start
ans.splice(0, 0, upper -i - 1)
}
// Print the stored in the list
document.write( '[');
ans.forEach(element => {
document.write(" "+element);
});
document.write( ' ' + ']');
}
// Driver Code
var N = 5, L = 3, R = 10;
// Function Call
bitonicSequence(N, L, R);
</script>
Producción:
[9, 10, 9, 8, 7]
Complejidad temporal : O(N)
Espacio auxiliar: O(1)