Dado un número entero N , la tarea es generar una permutación de elementos en el rango [1, N] en tal orden que la longitud de LIS desde el inicio sea igual a LIS desde el final de la array. Imprime -1 si no existe tal array.
Ejemplos:
Entrada: N = 5
Salida: [1, 3, 5, 4, 2]
Explicación:
LIS desde el lado izquierdo: [1, 3, 5]
LIS desde el lado derecho: [2, 4, 5]
Longitud del LIS desde la izquierda y lado derecho es lo mismo que es 3.Entrada: N = 7
Salida: [1, 3, 4, 7, 6, 5, 2]
Explicación:
LIS desde el lado izquierdo: [1, 3, 4, 7]
LIS desde el lado derecho: [2, 5, 6, 7]
La longitud de LIS desde el lado izquierdo y derecho es la misma que es 4.
Enfoque: Use la siguiente observación para resolver este problema:
- Si N = 2 , entonces tal array no existe.
- De lo contrario, si N es impar,
- Luego comience agregando 1 en el índice 0 y agregando 2 en el índice N-1.
- Ahora, agregue N en el índice N/2 . Después de eso, si N>3 , agregue los números restantes 3, 4, 5, .. . así sucesivamente los índices 1, 2, …, (N/2-1) .
- Ahora agregue los números restantes en orden decreciente desde el índice N/2+1 hasta N-2 .
- Si N es par,
- digamos 4 entonces solo tiene 1 solución posible: {2, 1, 4, 3}.
- Después de 4, suponga que N = 6 , luego simplemente agregue 6 al principio y 5 al final a la respuesta anterior para N = 4 que forma una array = [6, 2, 1, 4, 3, 5].
- Del mismo modo, para el próximo N par, simplemente agregue N en el índice 0 y N-1 en el último índice.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Si el tamaño mencionado es 2, devuelva -1.
- De lo contrario, agregue los elementos según la observación mencionada anteriormente.
- Devuelve la lista formada e imprime los elementos de la lista.
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 create array having
// same LIS from both sides
vector<int> equalLIS(int N)
{
// If N = 2 we can't create array
if (N == 2) {
vector<int> al;
al.push_back(-1);
return al;
}
// If N is odd it is possible
// to make an array
else if (N % 2 != 0) {
// Hash Map contains index
// with its value
map<int, int> lis;
// indices 0, N/2, and N-1
lis.insert({ 0, 1 });
lis.insert({ N - 1, 2 });
int mid = N / 2;
lis.insert({ mid, N });
if (N > 3) {
// Adding numbers 3, 4, ...
// and so on at index from
// 1 to mid-1 respectively
int val = 3;
for (int i = 1; i < mid; i++) {
lis.insert({ i, val });
val++;
}
// Adding remaining integers
// in decreasing order
// from mid+1 to N-2
val = N - 1;
for (int i = mid + 1; i < N - 1; i++) {
lis.insert({ i, val });
val--;
}
}
// Creating Array List
// which will use to form
// required array
vector<int> al;
// Traversing from smallest key
// to largest key in Hash Map
// and adding its value in list
for (int i = 0; i < N; i++) {
al.push_back(lis[i]);
}
// Returning formed array
return al;
}
else {
// Hash Map which contains
// index with its value
map<int, int> lis;
// Adding value for N=4 in Hash Map
lis.insert({ 0, 2 });
lis.insert({ 1, 1 });
lis.insert({ 2, 4 });
lis.insert({ 3, 3 });
int i = 3;
int idx = 0;
if (N >= 6) {
i++;
idx--;
// Adding new N at starting index
// and N-1 at last index
int val = 5;
while (val <= N) {
lis.insert({ i, val });
lis.insert({ idx, val + 1 });
idx--;
i++;
val += 2;
}
}
// Creating Array List
// which will use to form
// required array
vector<int> al;
// Traversing from minimum key
// to maximum key add
// adding its value in Array List
for (int j = idx + 1; j < i; j++) {
al.push_back(lis[j]);
}
// Returning formed array
return al;
}
}
// Driver Code
int main()
{
int N = 7;
vector<int> lis = equalLIS(N);
for (auto x : lis)
cout << x << " ";
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Driver Code
public static void main(String[] args)
{
int N = 7;
List<Integer> lis = equalLIS(N);
for (int x : lis)
System.out.print(x + " ");
}
// Function to create array having
// same LIS from both sides
public static List<Integer> equalLIS(int N)
{
// If N = 2 we can't create array
if (N == 2) {
List<Integer> al = new ArrayList<>();
al.add(-1);
return al;
}
// If N is odd it is possible
// to make an array
else if (N % 2 != 0) {
// Hash Map contains index
// with its value
Map<Integer, Integer> lis
= new HashMap<>();
// Adding 1, N, and 2 at
// indices 0, N/2, and N-1
lis.put(0, 1);
lis.put(N - 1, 2);
int mid = N / 2;
lis.put(mid, N);
if (N > 3) {
// Adding numbers 3, 4, ...
// and so on at index from
// 1 to mid-1 respectively
int val = 3;
for (int i = 1; i < mid; i++) {
lis.put(i, val);
val++;
}
// Adding remaining integers
// in decreasing order
// from mid+1 to N-2
val = N - 1;
for (int i = mid + 1;
i < N - 1; i++) {
lis.put(i, val);
val--;
}
}
// Creating Array List
// which will use to form
// required array
List<Integer> al
= new ArrayList<>();
// Traversing from smallest key
// to largest key in Hash Map
// and adding its value in list
for (int i = 0; i < N; i++) {
al.add(lis.get(i));
}
// Returning formed array
return al;
}
else {
// Hash Map which contains
// index with its value
Map<Integer, Integer> lis
= new HashMap<>();
// Adding value for N=4 in Hash Map
lis.put(0, 2);
lis.put(1, 1);
lis.put(2, 4);
lis.put(3, 3);
int i = 3;
int idx = 0;
if (N >= 6) {
i++;
idx--;
// Adding new N at starting index
// and N-1 at last index
int val = 5;
while (val <= N) {
lis.put(i, val);
lis.put(idx, val + 1);
idx--;
i++;
val += 2;
}
}
// Creating Array List
// which will use to form
// required array
List<Integer> al
= new ArrayList<>();
// Traversing from minimum key
// to maximum key add
// adding its value in Array List
for (int j = idx + 1; j < i; j++) {
al.add(lis.get(j));
}
// Returning formed array
return al;
}
}
}
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Driver Code
public static void Main(string[] args)
{
int N = 7;
List<int> lis = equalLIS(N);
for (int i = 0; i < lis.Count; i++)
Console.Write(lis[i] + " ");
}
// Function to create array having
// same LIS from both sides
public static List<int> equalLIS(int N)
{
// If N = 2 we can't create array
if (N == 2) {
List<int> al = new List<int>();
al.Add(-1);
return al;
}
// If N is odd it is possible
// to make an array
else if (N % 2 != 0) {
// Hash Map contains index
// with its value
Dictionary<int, int> lis
= new Dictionary<int, int>();
// Adding 1, N, and 2 at
// indices 0, N/2, and N-1
lis[0] = 1;
lis[N - 1] = 2;
int mid = N / 2;
lis[mid] = N;
if (N > 3) {
// Adding numbers 3, 4, ...
// and so on at index from
// 1 to mid-1 respectively
int val = 3;
for (int i = 1; i < mid; i++) {
lis[i] = val;
val++;
}
// Adding remaining integers
// in decreasing order
// from mid+1 to N-2
val = N - 1;
for (int i = mid + 1; i < N - 1; i++) {
lis[i] = val;
val--;
}
}
// Creating Array List
// which will use to form
// required array
List<int> al = new List<int>();
// Traversing from smallest key
// to largest key in Hash Map
// and adding its value in list
for (int i = 0; i < N; i++) {
al.Add(lis[i]);
}
// Returning formed array
return al;
}
else {
// Hash Map which contains
// index with its value
Dictionary<int, int> lis
= new Dictionary<int, int>();
// Adding value for N=4 in Hash Map
lis[0] = 2;
lis[1] = 1;
lis[2] = 4;
lis[3] = 3;
int i = 3;
int idx = 0;
if (N >= 6) {
i++;
idx--;
// Adding new N at starting index
// and N-1 at last index
int val = 5;
while (val <= N) {
lis[i] = val;
lis[idx] = val + 1;
idx -= 1;
i += 1;
val += 2;
}
}
// Creating Array List
// which will use to form
// required array
List<int> al = new List<int>();
// Traversing from minimum key
// to maximum key add
// adding its value in Array List
for (int j = idx + 1; j < i; j++) {
al.Add(lis[j]);
}
// Returning formed array
return al;
}
}
}
// This code is contributed by ukasp.
Producción
1 3 4 7 6 5 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)