Dados dos números enteros positivos K y N , la tarea es encontrar la permutación presente en el medio de todas las permutaciones de longitud máxima N , que consta de números enteros del rango [1, K], ordenados lexicográficamente.
Ejemplos:
Entrada: K = 3, N = 2
Salida: 2 1
Explicación: El orden lexicográfico de todas las permutaciones posibles es:
- {1}.
- {1, 1}
- {1, 2}
- {1, 3}
- {2}
- {2, 1}
- {2, 2}
- {2, 3}
- {3}
- {3, 1}
- {3, 2}
- {3, 3}
Por lo tanto, la secuencia lexicográficamente más pequeña del medio es (N/2) th (= 6th ) secuencia, que es {2, 1}.
Entrada: K = 2, N = 4
Salida: 1 2 2 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de una longitud [1, N] , que consta de números enteros de [1, K] . Almacene estos elementos en una array. Después de generar todas las subsecuencias, ordene la lista almacenada de subsecuencias e imprima el elemento central de la lista.
Complejidad temporal: O(N K )
Espacio auxiliar: O(N K )
Enfoque eficiente: el enfoque anterior se puede optimizar verificando la paridad de K , ya sea que K sea impar o par, y luego encuentre lexicográficamente la secuencia más pequeña en el medio en consecuencia. Siga los pasos a continuación para resolver el problema:
- Si el valor de K es par , entonces exactamente la mitad de las secuencias comienzan con un número entero K/2 o menos. Por lo tanto, la secuencia resultante es K/2 seguida de (N – 1) aparición de K .
- Si el valor K es impar , considere B como una secuencia que contiene N ocurrencias de (K + 1)/2 .
- Para una secuencia X , sea f(X) una secuencia tal que X i en X se reemplaza con (K + 1 − X i ) .
- La única excepción ocurre con los prefijos de B .
- Comience con la secuencia B y realice los siguientes pasos (N – 1)/2 veces:
- Si el último elemento de la secuencia actual es 1 , elimínelo.
- De lo contrario, disminuya el último elemento en 1 , y mientras la secuencia contenga menos de N elementos, e inserte K al final de la secuencia B.
- Después de completar los pasos anteriores, imprima la secuencia obtenida en la array B[] .
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 that finds the middle the
// lexicographical smallest sequence
void lexiMiddleSmallest(int K, int N)
{
// If K is even
if (K % 2 == 0) {
// First element is K/2
cout << K / 2 << " ";
// Remaining elements of the
// sequence are all integer K
for (int i = 0; i < N - 1; ++i) {
cout << K << " ";
}
cout << "\n";
exit(0);
}
// Stores the sequence when K
// is odd
vector<int> a(N, (K + 1) / 2);
// Iterate over the range [0, N/2]
for (int i = 0; i < N / 2; ++i) {
// Check if the sequence ends
// with in 1 or not
if (a.back() == 1) {
// Remove the sequence
// ending in 1
a.pop_back();
}
// If it doesn't end in 1
else {
// Decrement by 1
--a.back();
// Insert K to the sequence
// till its size is N
while ((int)a.size() < N) {
a.push_back(K);
}
}
}
// Print the sequence stored
// in the vector
for (auto i : a) {
cout << i << " ";
}
cout << "\n";
}
// Driver Code
int main()
{
int K = 2, N = 4;
lexiMiddleSmallest(K, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function that finds the middle the
// lexicographical smallest sequence
static void lexiMiddleSmallest(int K, int N)
{
// If K is even
if (K % 2 == 0) {
// First element is K/2
System.out.print(K / 2 + " ");
// Remaining elements of the
// sequence are all integer K
for (int i = 0; i < N - 1; ++i) {
System.out.print(K + " ");
}
System.out.println();
return;
}
// Stores the sequence when K
// is odd
ArrayList<Integer> a = new ArrayList<Integer>();
// Iterate over the range [0, N/2]
for (int i = 0; i < N / 2; ++i) {
// Check if the sequence ends
// with in 1 or not
if (a.get(a.size() - 1) == 1) {
// Remove the sequence
// ending in 1
a.remove(a.size() - 1);
}
// If it doesn't end in 1
else {
// Decrement by 1
int t = a.get(a.size() - 1) - 1;
a.set(a.get(a.size() - 1), t);
// Insert K to the sequence
// till its size is N
while (a.size() < N) {
a.add(K);
}
}
}
// Print the sequence stored
// in the vector
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int K = 2, N = 4;
lexiMiddleSmallest(K, N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach # Function that finds the middle the # lexicographical smallest sequence def lexiMiddleSmallest(K, N): # If K is even if (K % 2 == 0): # First element is K/2 print(K // 2,end=" ") # Remaining elements of the # sequence are all integer K for i in range(N - 1): print(K, end = " ") print() return # Stores the sequence when K # is odd a = [(K + 1) // 2]*(N) # Iterate over the range [0, N/2] for i in range(N//2): # Check if the sequence ends # with in 1 or not if (a[-1] == 1): # Remove the sequence # ending in 1 del a[-1] # If it doesn't end in 1 else: # Decrement by 1 a[-1] -= 1 # Insert K to the sequence # till its size is N while (len(a) < N): a.append(K) # Print sequence stored # in the vector for i in a: print(i, end = " ") print() # Driver Code if __name__ == '__main__': K, N = 2, 4 lexiMiddleSmallest(K, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function that finds the middle the
// lexicographical smallest sequence
static void lexiMiddleSmallest(int K, int N)
{
// If K is even
if (K % 2 == 0) {
// First element is K/2
Console.Write(K / 2 + " ");
// Remaining elements of the
// sequence are all integer K
for (int i = 0; i < N - 1; ++i) {
Console.Write(K + " ");
}
Console.WriteLine();
return;
}
// Stores the sequence when K
// is odd
List<int> a = new List<int>();
// Iterate over the range [0, N/2]
for (int i = 0; i < N / 2; ++i) {
// Check if the sequence ends
// with in 1 or not
if (a[a.Count - 1] == 1) {
// Remove the sequence
// ending in 1
a.Remove(a.Count - 1);
}
// If it doesn't end in 1
else {
// Decrement by 1
a[a.Count - 1] -= 1;
// Insert K to the sequence
// till its size is N
while ((int)a.Count < N) {
a.Add(K);
}
}
}
// Print the sequence stored
// in the vector
foreach(int i in a) { Console.Write(i + " "); }
Console.WriteLine();
}
// Driver Code
public static void Main()
{
int K = 2, N = 4;
lexiMiddleSmallest(K, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program for the above approach
// Function that finds the middle the
// lexicographical smallest sequence
function lexiMiddleSmallest(K, N)
{
// If K is even
if (K % 2 == 0) {
// First element is K/2
document.write(K / 2 + " ");
// Remaining elements of the
// sequence are all integer K
for (let i = 0; i < N - 1; ++i) {
document.write(K + " ");
}
document.write("<br/>");
return;
}
// Stores the sequence when K
// is odd
let a = [];
// Iterate over the range [0, N/2]
for (let i = 0; i < N / 2; ++i) {
// Check if the sequence ends
// with in 1 or not
if (a[a.length - 1] == 1) {
// Remove the sequence
// ending in 1
a.pop(a.length - 1);
}
// If it doesn't end in 1
else {
// Decrement by 1
a[a.length - 1] -= 1;
// Insert K to the sequence
// till its size is N
while (a.length < N) {
a.push(K);
}
}
}
// Print the sequence stored
// in the vector
for(let i in a) { document.write(i + " "); }
document.write("<br/>");
}
// Driver Code
let K = 2, N = 4;
lexiMiddleSmallest(K, N);
</script>
Producción:
1 2 2 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por huzaifa0602 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA