Dados dos enteros positivos N y K , la tarea es construir una permutación de los primeros N números naturales tal que todas las posibles diferencias absolutas entre elementos adyacentes sean K .
Ejemplos:
Entrada: N = 3, K = 1
Salida: 1 2 3
Explicación: Considerando la permutación {1, 2, 3}, todas las posibles diferencias absolutas únicas de elementos adyacentes son {1}. Dado que la cuenta es 1(= K), imprima la secuencia {1, 2, 3} como la permutación resultante.Entrada: N = 3, K = 2
Salida: 1 3 2
El enfoque ingenuo y el enfoque de dos puntos de este problema ya se discuten aquí . Este artículo analiza un enfoque diferente deque .
Enfoque: es fácil ver que se pueden generar respuestas para todos los valores de K entre [1, N-1] . Para cualquier K fuera de este rango, no existe respuesta. Para resolver el problema, mantenga una cola de dos extremos para todos los elementos actuales y un vector para almacenar la secuencia. Además, mantenga un valor booleano que le ayudará a determinar si aparece el elemento frontal o posterior. Iterar el elemento restante y si K es mayor que 1 , empujar el elemento de acuerdo con el valor booleano y disminuir K en 1 . Voltee el valor booleano para que todas las diferencias restantes tengan el valor 1. Siga los pasos a continuación para resolver el problema:
- Si K es mayor que igual a N o menor que 1, imprima -1 y regrese como si no existiera tal secuencia.
- Inicialice un deque dq[] para mantener el orden de los elementos.
- Iterar sobre el rango [2, N] usando la variable i y empujar i en la parte posterior de deque dq[] .
- Inicializa una variable booleana frente como verdadera.
- Inicialice un vector ans[] para almacenar la respuesta y presione 1 en el vector ans[].
- Si K es mayor que 1, reste 1 de K y xor el valor de frente con 1.
- Itere sobre el rango [2, N] usando la variable i y verifique:
- Si el frente es 1 , entonces saque el frente del deque dq[] y empújelo en el vector ans[] de lo contrario, saque el reverso del deque dq[] y empújelo en el vector ans[] . Además, si K es mayor que entonces, resta 1 de K y xor el valor de frente con 1.
- Recorra la array ans[] e imprima sus elementos.
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 calculate the required array
void K_ValuesArray(int N, int K)
{
// Check for base cases
if (K < 1 || K >= N) {
cout << -1;
return;
}
// Maintain a deque to store the
// elements from [1, N];
deque<int> dq;
for (int i = 2; i <= N; i++) {
dq.push_back(i);
}
// Maintain a boolean value which will
// tell from where to pop the element
bool front = true;
// Create a vector to store the answer
vector<int> ans;
// Push 1 in the answer initially
ans.push_back(1);
// Push the remaining elements
if (K > 1) {
front ^= 1;
K--;
}
// Iterate over the range
for (int i = 2; i <= N; i++) {
if (front) {
int val = dq.front();
dq.pop_front();
// Push this value in
// the ans vector
ans.push_back(val);
if (K > 1) {
K--;
// Flip the boolean
// value
front ^= 1;
}
}
else {
int val = dq.back();
dq.pop_back();
// Push value in ans vector
ans.push_back(val);
if (K > 1) {
K--;
// Flip boolean value
front ^= 1;
}
}
}
// Print Answer
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
int N = 7, K = 1;
K_ValuesArray(N, K);
return 0;
}
Java
// Java Program for the above approach
import java.util.*;
class GFG{
// Function to calculate the required array
static void K_ValuesArray(int N, int K)
{
// Check for base cases
if (K < 1 || K >= N) {
System.out.print(-1);
return;
}
// Maintain a deque to store the
// elements from [1, N];
Deque<Integer> dq = new LinkedList<Integer>();
for (int i = 2; i <= N; i++) {
dq.add(i);
}
// Maintain a boolean value which will
// tell from where to pop the element
boolean front = true;
// Create a vector to store the answer
Vector<Integer> ans = new Vector<Integer>();
// Push 1 in the answer initially
ans.add(1);
// Push the remaining elements
if (K > 1) {
front ^=true;
K--;
}
// Iterate over the range
for (int i = 2; i <= N; i++) {
if (front) {
int val = dq.peek();
dq.removeFirst();
// Push this value in
// the ans vector
ans.add(val);
if (K > 1) {
K--;
// Flip the boolean
// value
front ^=true;
}
}
else {
int val = dq.getLast();
dq.removeLast();
// Push value in ans vector
ans.add(val);
if (K > 1) {
K--;
// Flip boolean value
front ^=true;
}
}
}
// Print Answer
for (int i = 0; i < N; i++) {
System.out.print(ans.get(i)+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 7, K = 1;
K_ValuesArray(N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# python Program for the above approach
from collections import deque
# Function to calculate the required array
def K_ValuesArray(N, K):
# Check for base cases
if (K < 1 or K >= N):
print("-1")
return
# Maintain a deque to store the
# elements from [1, N];
dq = deque()
for i in range(2, N + 1):
dq.append(i)
# Maintain a boolean value which will
# tell from where to pop the element
front = True
# Create a vector to store the answer
ans = []
# Push 1 in the answer initially
ans.append(1)
# Push the remaining elements
if (K > 1):
front ^= 1
K -= 1
# Iterate over the range
for i in range(2, N+1):
if (front):
val = dq.popleft()
# Push this value in
# the ans vector
ans.append(val)
if (K > 1):
K -= 1
# Flip the boolean
# value
front ^= 1
else:
val = dq.pop()
# Push value in ans vector
ans.append(val)
if (K > 1):
K -= 1
# Flip boolean value
front ^= 1
# Print Answer
for i in range(0, N):
print(ans[i], end=" ")
# Driver Code
if __name__ == "__main__":
N = 7
K = 1
K_ValuesArray(N, K)
# This code is contributed by rakeshsahni
C#
// C# Program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate the required array
static void K_ValuesArray(int N, int K)
{
// Check for base cases
if (K < 1 || K >= N)
{
Console.Write(-1);
return;
}
// Maintain a deque to store the
// elements from [1, N];
LinkedList<int> dq = new LinkedList<int>();
for (int i = 2; i <= N; i++)
{
dq.AddLast(i);
}
// Maintain a boolean value which will
// tell from where to pop the element
bool front = true;
// Create a vector to store the answer
List<int> ans = new List<int>();
// Push 1 in the answer initially
ans.Add(1);
// Push the remaining elements
if (K > 1)
{
front ^= true;
K--;
}
// Iterate over the range
for (int i = 2; i <= N; i++)
{
if (front)
{
int val = dq.First.Value;
dq.RemoveFirst();
// Push this value in
// the ans vector
ans.Add(val);
if (K > 1)
{
K--;
// Flip the boolean
// value
front ^= true;
}
}
else
{
int val = dq.Last.Value;
dq.RemoveLast();
// Push value in ans vector
ans.Add(val);
if (K > 1)
{
K--;
// Flip boolean value
front ^= true;
}
}
}
// Print Answer
for (int i = 0; i < N; i++)
{
Console.Write(ans[i] + " ");
}
}
// Driver Code
public static void Main()
{
int N = 7, K = 1;
K_ValuesArray(N, K);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// Javascript Program for the above approach
// Function to calculate the required array
function K_ValuesArray(N, K) {
// Check for base cases
if (K < 1 || K >= N) {
document.write(-1);
return;
}
// Maintain a deque to store the
// elements from [1, N];
let dq = new Array();
for (let i = 2; i <= N; i++) {
dq.push(i);
}
// Maintain a boolean value which will
// tell from where to pop the element
let front = true;
// Create a vector to store the answer
let ans = new Array();
// Push 1 in the answer initially
ans.push(1);
// Push the remaining elements
if (K > 1) {
front ^= true;
K--;
}
// Iterate over the range
for (let i = 2; i <= N; i++) {
if (front) {
let val = dq[0];
dq.shift();
// Push this value in
// the ans vector
ans.push(val);
if (K > 1) {
K--;
// Flip the boolean
// value
front ^= true;
}
}
else {
let val = dq.Last.Value;
dq.pop();
// Push value in ans vector
ans.push(val);
if (K > 1) {
K--;
// Flip boolean value
front ^= true;
}
}
}
// Print Answer
for (let i = 0; i < N; i++) {
document.write(ans[i] + " ");
}
}
// Driver Code
let N = 7, K = 1;
K_ValuesArray(N, K);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
1 2 3 4 5 6 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA