Genere una permutación de 1 a N sin diferencia de elementos adyacentes como 1

Dado un número entero N , la tarea es construir una permutación de 1 a N donde ningún elemento adyacente tenga una diferencia de 1. Si no existe tal permutación, imprima -1.

La permutación de 1 a N tiene todos los números de 1 a N presentes exactamente una vez.

Ejemplos:

Entrada: N = 5 
Salida: 4 2 5 3 1
Explicación: En cuanto a N = 5, [ 4 2 5 3 1 ] es la única permutación donde la diferencia entre los elementos adyacentes no es 1.

Entrada: N = 3
Salida: -1

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

• La diferencia entre dos números pares cualesquiera es mayor que 1 y, de manera similar, para todos los elementos impares su diferencia es mayor que 1
• Por lo tanto, imprima primero todos los números pares seguidos de los números impares.

Siga los pasos mencionados a continuación para implementar el enfoque anterior:

• Si N es menor o igual a 3, entonces tal permutación no es posible.
• Si N es par, primero imprima todos los números pares del 2 al N , y luego todos los impares del 1 al N – 1 imprima todos los números impares.
• Si la N es impar, imprima todos los números pares del 2 al N – 1 y luego todos los números impares del 1 al N.

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

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the permutation
// which satisfies the given condition
vector<int> permutation(int n)
{
    vector<int> ans;
    if (n <= 3) {
        ans.push_back(-1);
    }
 
    // If n is even
    if (n % 2 == 0) {
        for (int i = 2; i <= n; i += 2) {
            ans.push_back(i);
        }
        for (int i = 1; i < n; i += 2) {
            ans.push_back(i);
        }
    }
 
    // If n is odd
    else {
        for (int i = 2; i <= n - 1; i += 2) {
            ans.push_back(i);
        }
        for (int j = 1; j <= n; j += 2) {
            ans.push_back(j);
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5;
    vector<int> ans = permutation(N);
    for (int x : ans)
        cout << x << " ";
    return 0;
}

// Java code for the above approach
import java.util.*;
 
class GFG {
 
  // Function to find the permutation
  // which satisfies the given condition
  static List<Integer> permutation(int n)
  {
    List<Integer> ans = new ArrayList<>();
    if (n <= 3) {
      ans.add(-1);
    }
 
    // If n is even
    if (n % 2 == 0) {
      for (int i = 2; i <= n; i += 2) {
        ans.add(i);
      }
      for (int i = 1; i < n; i += 2) {
        ans.add(i);
      }
    }
 
    // If n is odd
    else {
      for (int i = 2; i <= n - 1; i += 2) {
        ans.add(i);
      }
      for (int j = 1; j <= n; j += 2) {
        ans.add(j);
      }
    }
    return ans;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 5;
    List<Integer> ans = permutation(N);
    for (Integer x : ans)
      System.out.print(x + " ");
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program to generate permutation of 1 to n
# with no adjacent element difference as 1
def permutation(n):
 
    # for storing the resultant permutations
    ans = []
 
    if n <= 3:
        ans.append(-1)
 
    # if n is even
    if n % 2 == 0:
        i = 0
        while i <= n:
            ans.append(i)
            i += 2
        i = 1
        while i < n:
            ans.append(i)
            i += 2
 
    # if n is odd
    else:
        i = 2
        while i <= n-1:
            ans.append(i)
            i += 2
        j = 1
        while j <= n:
            ans.append(j)
            j += 2
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    n = 5
    ans = permutation(n)
    for i in ans:
        print(i, end=" ")
 
        # This code is contributed by Amnindersingh1414.

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to find the permutation
  // which satisfies the given condition
  static List<int> permutation(int n) {
    List<int> ans = new List<int>();
    if (n <= 3) {
      ans.Add(-1);
    }
 
    // If n is even
    if (n % 2 == 0) {
      for (int i = 2; i <= n; i += 2) {
        ans.Add(i);
      }
      for (int i = 1; i < n; i += 2) {
        ans.Add(i);
      }
    }
 
    // If n is odd
    else {
      for (int i = 2; i <= n - 1; i += 2) {
        ans.Add(i);
      }
      for (int j = 1; j <= n; j += 2) {
        ans.Add(j);
      }
    }
    return ans;
  }
 
  // Driver Code
  public static void Main(String[] args) {
    int N = 5;
    List<int> ans = permutation(N);
    foreach (int x in ans)
      Console.Write(x + " ");
  }
}
 
// This code is contributed by gauravrajput1

  <script>
        // JavaScript code for the above approach
 
// Function to find the permutation
// which satisfies the given condition
function permutation(n)
{
    let ans=[];
    if (n <= 3) {
        ans.push(-1);
    }
 
    // If n is even
    if (n % 2 == 0) {
        for (let i = 2; i <= n; i += 2) {
            ans.push(i);
        }
        for (let i = 1; i < n; i += 2) {
            ans.push(i);
        }
    }
 
    // If n is odd
    else {
        for (let i = 2; i <= n - 1; i += 2) {
            ans.push(i);
        }
        for (let j = 1; j <= n; j += 2) {
            ans.push(j);
        }
    }
    return ans;
}
 
// Driver Code
 
    let N = 5;
    let ans = permutation(N);
    for (let x of ans)
        document.write( x + " ");
    
      // This code is contributed by Potta Lokesh
 
    </script>

2 4 1 3 5 

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