Genere una permutación de longitud N tal que la diferencia absoluta entre elementos adyacentes esté presente en el rango [2, 4]

Dado un entero positivo N , la tarea es construir una permutación de los primeros N números naturales tal que la diferencia absoluta entre los elementos adyacentes sea 2 , 3 o 4 . Si no es posible construir tal permutación, imprima «-1» .

Ejemplos:

Entrada: N = 4
Salida: 3 1 4 2
Explicación:
Considere una permutación {3, 1, 4, 2}. Ahora, la diferencia absoluta entre elementos adyacentes es {2, 3, 2}.

Entrada: N = 9
Salida: 9 7 5 3 1 4 2 6 8 

Enfoque: El problema dado se puede resolver agrupando elementos pares e impares consecutivos para construir la permutación . Siga los pasos a continuación para resolver el problema:

• Si el valor de N es menor que 4 , imprima -1 ya que es imposible construir una permutación de acuerdo con las condiciones dadas para N menor que 4 .
• Inicialice una variable, diga i como N , y realice los siguientes pasos a continuación:
  • Si el valor de i es par , disminuya el valor de i en 1 .
  • Iterar hasta que el valor de i sea al menos 1 e imprimir el valor de i y disminuir el valor de i en 2 .
  • Imprime 4 y 2 y actualiza el valor de i a 6 .
  • Iterar en el rango [i, N] e imprimir el valor de i e incrementar el valor de i en 2 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the permutation of
// size N with absolute difference of
// adjacent elements in range [2, 4]
void getPermutation(int N)
{
    // If N is less than 4
    if (N <= 3) {
        cout << -1;
        return;
    }
 
    int i = N;
 
    // Check if N is even
    if (N % 2 == 0)
        i--;
 
    // Traverse through odd integers
    while (i >= 1) {
        cout << i << " ";
        i -= 2;
    }
 
    cout << 4 << " " << 2 << " ";
 
    // Update the value of i
    i = 6;
 
    // Traverse through even integers
    while (i <= N) {
        cout << i << " ";
        i += 2;
    }
}
 
// Driver Code
int main()
{
    int N = 9;
    getPermutation(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to print the permutation of
// size N with absolute difference of
// adjacent elements in range [2, 4]
static void getPermutation(int N)
{
     
    // If N is less than 4
    if (N <= 3)
    {
        System.out.print(-1);
        return;
    }
 
    int i = N;
 
    // Check if N is even
    if (N % 2 == 0)
        i--;
 
    // Traverse through odd integers
    while (i >= 1)
    {
        System.out.print(i + " ");
        i -= 2;
    }
 
    System.out.print(4 + " " + 2 +" ");
 
    // Update the value of i
    i = 6;
 
    // Traverse through even integers
    while (i <= N)
    {
        System.out.print(i + " ");
        i += 2;
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 9;
     
    getPermutation(N);
}   
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# Function to print permutation of
# size N with absolute difference of
# adjacent elements in range [2, 4]
def getPermutation(N):
   
    # If N is less than 4
    if (N <= 3):
        print(-1)
        return
 
    i = N
 
    # Check if N is even
    if (N % 2 == 0):
        i -= 1
 
    # Traverse through odd integers
    while (i >= 1):
        print(i, end = " ")
        i -= 2
 
    print(4, 2, end = " ")
 
    # Update the value of i
    i = 6
 
    # Traverse through even integers
    while (i <= N):
        print( i, end = " ")
        i += 2
 
# Driver Code
if __name__ == '__main__':
    N = 9
    getPermutation(N)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to print the permutation of
// size N with absolute difference of
// adjacent elements in range [2, 4]
static void getPermutation(int N)
{
     
    // If N is less than 4
    if (N <= 3)
    {
         
        Console.Write(-1);
        return;
    }
 
    int i = N;
 
    // Check if N is even
    if (N % 2 == 0)
        i--;
 
    // Traverse through odd integers
    while (i >= 1)
    {
        Console.Write(i + " ");
        i -= 2;
    }
 
    Console.Write(4 + " " + 2 +" ");
 
    // Update the value of i
    i = 6;
 
    // Traverse through even integers
    while (i <= N)
    {
        Console.Write(i +" ");
        i += 2;
    }
}
 
// Driver Code
public static void Main()
{
    int N = 9;
     
    getPermutation(N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
 
// JavaScript program for the above approach
 
// Function to print the permutation of
// size N with absolute difference of
// adjacent elements in range [2, 4]
function getPermutation(N)
{
     
    // If N is less than 4
    if (N <= 3)
    {
        document.write(-1);
        return;
    }
 
    let i = N;
 
    // Check if N is even
    if (N % 2 == 0)
        i--;
 
    // Traverse through odd integers
    while (i >= 1)
    {
        document.write(i + " ");
        i -= 2;
    }
 
    document.write(4 + " " + 2 + " ");
 
    // Update the value of i
    i = 6;
 
    // Traverse through even integers
    while (i <= N)
    {
        document.write(i + " ");
        i += 2;
    }
}
 
// Driver Code
let N = 9;
 
getPermutation(N);
 
// This code is contributed by Potta Lokesh
 
</script>

9 7 5 3 1 4 2 6 8

Complejidad temporal: O(N)
Espacio auxiliar: O(1)