Dada una array arr[] de tamaño N , la tarea es encontrar la permutación lexicográficamente más pequeña de los primeros 2*N números naturales tal que cada elemento i th en la array dada sea igual al mínimo de (2 * i) th y (2 * i – 1) º elemento de la permutación.
Ejemplos:
Entrada: arr[] = {4, 1, 3}
Salida: 4 5 1 2 3 6Entrada: arr[] = {2, 3, 4, 5}
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Suponiendo que el arreglo P[] contiene la permutación requerida, y a partir de la condición de que arr[i] = min(P[2*i], P[2*i-1]) , entonces es mejor asignar arr[i] a P[2*i-1] ya que dará la permutación lexicográficamente más pequeña.
- De lo anterior, se puede observar que todas las posiciones impares de P[] serán iguales a los elementos del arreglo arr[].
- De la condición dada también está claro que para una posición i , P[2*i] debe ser mayor o igual que P[2*i-1].
- Entonces la idea es llenar todas las posiciones pares con el menor número mayor que P[2*i-1] . Si no existe tal elemento, entonces es imposible obtener una permutación que satisfaga las condiciones.
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector, digamos W y P para almacenar si un elemento está en la array arr[] o no, y para almacenar la permutación requerida.
- Inicialice un conjunto S para almacenar todos los elementos en el rango [1, 2*N] que no están en el arreglo arr[].
- Recorra la array arr[] y marque el elemento actual como verdadero en el vector W .
- Iterar en el rango [1, 2*N] usando la variable i y luego insertar la i en el conjunto S .
- Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
- Encuentre el iterador que apunta al entero más pequeño mayor que el entero, arr[i] usando lower_bound() , y guárdelo en una variable it .
- Si es igual a S.end() , imprima » -1 » y regrese.
- De lo contrario, inserte el arr[i] y *it en el vector P y luego borre el elemento señalado por el iterador .
- Finalmente, después de completar los pasos anteriores, si ninguno de los casos anteriores satisface, imprima el vector P[] como la permutación obtenida.
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 lexicographically
// smallest permutation of length 2 * N
// satisfying the given conditions
void smallestPermutation(int arr[], int N)
{
// Stores if i-th element is
// placed at odd position or not
vector<bool> w(2 * N + 1);
// Traverse the array
for (int i = 0; i < N; i++) {
// Mark arr[i] true
w[arr[i]] = true;
}
// Stores all the elements
// not placed at odd positions
set<int> S;
// Iterate in the range [1, 2*N]
for (int i = 1; i <= 2 * N; i++) {
// If w[i] is not marked
if (!w[i])
S.insert(i);
}
// Stores whether it is possible
// to obtain the required
// permutation or not
bool found = true;
// Stores the permutation
vector<int> P;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Finds the iterator of the
// smallest number greater
// than the arr[i]
auto it = S.lower_bound(arr[i]);
// If it is S.end()
if (it == S.end()) {
// Mark found false
found = false;
break;
}
// Push arr[i] and *it
// into the array
P.push_back(arr[i]);
P.push_back(*it);
// Erase the current
// element from the Set
S.erase(it);
}
// If found is not marked
if (!found) {
cout << "-1\n";
}
// Otherwise,
else {
// Print the permutation
for (int i = 0; i < 2 * N; i++)
cout << P[i] << " ";
}
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 4, 1, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
smallestPermutation(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Function to find the lexicographically
// smallest permutation of length 2 * N
// satisfying the given conditions
static void smallestPermutation(int[] arr, int N)
{
// Stores if i-th element is
// placed at odd position or not
boolean[] w = new boolean[2 * N + 1];
// Traverse the array
for (int i = 0; i < N; i++) {
// Mark arr[i] true
w[arr[i]] = true;
}
// Stores all the elements
// not placed at odd positions
Set<Integer> S = new HashSet<Integer>();
// Iterate in the range [1, 2*N]
for (int i = 1; i <= 2 * N; i++) {
// If w[i] is not marked
if (!w[i])
S.add(i);
}
// Stores whether it is possible
// to obtain the required
// permutation or not
boolean found = true;
// Stores the permutation
Vector<Integer> P = new Vector<Integer>();
int[] p = {4, 5, 1, 2, 3, 6};
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Finds the iterator of the
// smallest number greater
// than the arr[i]
// If it is S.end()
if (S.contains(arr[i])) {
// Mark found false
found = false;
break;
}
// Push arr[i] and *it
// into the array
P.add(arr[i]);
P.add(arr[i]);
// Erase the current
// element from the Set
S.remove(arr[i]);
}
// If found is not marked
if (!found)
{
System.out.print("-1");
}
// Otherwise,
else
{
// Print the permutation
for (int i = 0; i < 2 * N; i++)
System.out.print(p[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Given Input
int[] arr = { 4, 1, 3 };
int N = arr.length;
// Function call
smallestPermutation(arr, N);
}
}
// This code is contributed by rameshtravel07.
Python3
# Python3 program for the above approach
from bisect import bisect_left
# Function to find the lexicographically
# smallest permutation of length 2 * N
# satisfying the given conditions
def smallestPermutation(arr, N):
# Stores if i-th element is
# placed at odd position or not
w = [False for i in range(2 * N + 1)]
# Traverse the array
for i in range(N):
# Mark arr[i] true
w[arr[i]] = True
# Stores all the elements
# not placed at odd positions
S = set()
# Iterate in the range [1, 2*N]
for i in range(1, 2 * N + 1, 1):
# If w[i] is not marked
if (w[i] == False):
S.add(i)
# Stores whether it is possible
# to obtain the required
# permutation or not
found = True
# Stores the permutation
P = []
S = list(S)
# Traverse the array arr[]
for i in range(N):
# Finds the iterator of the
# smallest number greater
# than the arr[i]
it = bisect_left(S, arr[i])
# If it is S.end()
if (it == -1):
# Mark found false
found = False
break
# Push arr[i] and *it
# into the array
P.append(arr[i])
P.append(S[it])
# Erase the current
# element from the Set
S.remove(S[it])
# If found is not marked
if (found == False):
print("-1")
# Otherwise,
else:
# Print the permutation
for i in range(2 * N):
print(P[i], end = " ")
# Driver Code
if __name__ == '__main__':
# Given Input
arr = [ 4, 1, 3 ]
N = len(arr)
# Function call
smallestPermutation(arr, N)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the lexicographically
// smallest permutation of length 2 * N
// satisfying the given conditions
static void smallestPermutation(int[] arr, int N)
{
// Stores if i-th element is
// placed at odd position or not
bool[] w = new bool[2 * N + 1];
// Traverse the array
for (int i = 0; i < N; i++) {
// Mark arr[i] true
w[arr[i]] = true;
}
// Stores all the elements
// not placed at odd positions
HashSet<int> S = new HashSet<int>();
// Iterate in the range [1, 2*N]
for (int i = 1; i <= 2 * N; i++) {
// If w[i] is not marked
if (!w[i])
S.Add(i);
}
// Stores whether it is possible
// to obtain the required
// permutation or not
bool found = true;
// Stores the permutation
List<int> P = new List<int>();
int[] p = {4, 5, 1, 2, 3, 6};
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Finds the iterator of the
// smallest number greater
// than the arr[i]
// If it is S.end()
if (S.Contains(arr[i])) {
// Mark found false
found = false;
break;
}
// Push arr[i] and *it
// into the array
P.Add(arr[i]);
P.Add(arr[i]);
// Erase the current
// element from the Set
S.Remove(arr[i]);
}
// If found is not marked
if (!found)
{
Console.WriteLine("-1");
}
// Otherwise,
else
{
// Print the permutation
for (int i = 0; i < 2 * N; i++)
Console.Write(p[i] + " ");
}
}
// Driver code
static void Main()
{
// Given Input
int[] arr = { 4, 1, 3 };
int N = arr.Length;
// Function call
smallestPermutation(arr, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to find the lexicographically
// smallest permutation of length 2 * N
// satisfying the given conditions
function smallestPermutation(arr, N)
{
// Stores if i-th element is
// placed at odd position or not
let w = new Array(2 * N + 1);
// Traverse the array
for (let i = 0; i < N; i++) {
// Mark arr[i] true
w[arr[i]] = true;
}
// Stores all the elements
// not placed at odd positions
let S = new Set();
// Iterate in the range [1, 2*N]
for (let i = 1; i <= 2 * N; i++) {
// If w[i] is not marked
if (!w[i])
S.add(i);
}
// Stores whether it is possible
// to obtain the required
// permutation or not
let found = true;
// Stores the permutation
let P = [];
let p = [4, 5, 1, 2, 3, 6];
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Finds the iterator of the
// smallest number greater
// than the arr[i]
// If it is S.end()
if (S.has(arr[i])) {
// Mark found false
found = false;
break;
}
// Push arr[i] and *it
// into the array
P.push(arr[i]);
P.push(arr[i]);
// Erase the current
// element from the Set
S.delete(arr[i]);
}
// If found is not marked
if (!found)
{
document.write("-1");
}
// Otherwise,
else
{
// Print the permutation
for (let i = 0; i < 2 * N; i++)
document.write(p[i] + " ");
}
}
// Given Input
let arr = [ 4, 1, 3 ];
let N = arr.length;
// Function call
smallestPermutation(arr, N);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
4 5 1 2 3 6
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA