Permutación de los primeros N elementos con diferencia adyacente absoluta en orden creciente

Dado un entero positivo N, la tarea es construir una permutación de 1 a N tal que la diferencia absoluta de elementos esté en orden estrictamente creciente. 

Nota: N no puede ser 0 o 1.

Ejemplos :

Entrada : N = 10
Salida : 6 5 7 4 8 3 9 2 10 1
Explicación : abs(6 – 5) es decir, 1 < abs(5 – 7) es decir, 2 < abs(7 – 4) es decir, 3 …. < abs(2 – 10) es decir, 8 < abs(10 – 1) es decir, 9

Entrada : 3
Salida : 2 3 1 
Explicación : abs(2 – 3) = 1 y abs(3 – 1) = 2, 1 < 2, por lo que está en orden estrictamente creciente.

Enfoque : El problema se puede resolver en base a la siguiente observación:

Observación:

Digamos que tiene i = 1 y j = N, la diferencia absoluta más grande que se hace es restar 1 y N = (N – 1)

La próxima vez, i incremento en 1, i = 2 y j permanece igual, es decir, N, por lo que la diferencia absoluta es = (N – 2).
La próxima vez, i permanece igual, es decir, 2 y j disminuyen en 1, j = N-1, por lo tanto, la diferencia absoluta es = (N – 1 – 2) = (N – 3).
La próxima vez, incremento en 1, i = 3 y j permanece igual, es decir, N-1, por lo tanto, la diferencia absoluta es = (N – 1 – 3) = (N – 4).
La próxima vez, i permanece igual, es decir, 3 y j disminuyen en 1, j = N-2, por lo tanto, la diferencia absoluta es = (N – 2 – 3) = (N – 5)……

Ahora, así van las series, y por fin dos condiciones posibles,

• Cuando i = j + 1, [si N es impar], diferencia absoluta = 1
• O, j = i + 1, [Si N es par], diferencia absoluta = 1

Entonces, de esta manera la serie se convierte en N dada, serie = (N – 1), (N – 2), (N – 3), …. 3, 2, 1.

Siga los pasos a continuación para resolver el problema:

• Inicializa un puntero i = 1 y j = N .
• Declare una array de tamaño N .
• Ejecute un ciclo (usando el iterador x ) de 0 a N – 1 .
  • Si x es par entonces se establece, arr[x] = i e incrementa i en 1 .
  • De lo contrario, establezca arr[x] = j y disminuya j en 1 .
• Después de ejecutar el ciclo, imprima la array en orden inverso.

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

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print valid permutation of N
void findPerm(int n)
{
 
    // Initialize the pointers
    int i = 1, j = n;
 
    // Declare an array of size N
    int arr[n];
 
    // Constructing the array
    for (int x = 0; x < n; x++) {
        if (x & 1)
            arr[x] = j--;
        else
            arr[x] = i++;
    }
 
    // Printing the array
    for (int x = (n - 1); x >= 0; x--) {
        cout << arr[x] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 10;
 
    // Function Call
    findPerm(N);
    return 0;
}

// Java code to implement the above approach
 
public class GFG {
     
// Function to print valid permutation of N
static void findPerm(int n)
{
 
    // Initialize the pointers
    int i = 1, j = n;
 
    // Declare an array of size N
    int arr[] = new int[n];
 
    // Constructing the array
    for (int x = 0; x < n; x++) {
        if ((x & 1) == 1)
            arr[x] = j--;
        else
            arr[x] = i++;
    }
 
    // Printing the array
    for (int x = (n - 1); x >= 0; x--) {
        System.out.print(arr[x]+" ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 10;
 
    // Function Call
    findPerm(N);
}
 
}
 
// This code is contributed by AnkThon

# python3 code to implement the above approach
 
# Function to print valid permutation of N
def findPerm(n):
 
    # Initialize the pointers
    i, j = 1, n
 
    # Declare an array of size N
    arr = [0 for _ in range(n)]
 
    # Constructing the array
    for x in range(0, n):
        if (x & 1):
            arr[x] = j
            j -= 1
        else:
            arr[x] = i
            i += 1
 
    # Printing the array
    for x in range(n-1, -1, -1):
        print(arr[x], end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    N = 10
 
    # Function Call
    findPerm(N)
 
    # This code is contributed by rakeshsahni

// C# code to implement the above approach
using System;
 
public class GFG {
 
  // Function to print valid permutation of N
  static void findPerm(int n)
  {
 
    // Initialize the pointers
    int i = 1, j = n;
 
    // Declare an array of size N
    int[] arr = new int[n];
 
    // Constructing the array
    for (int x = 0; x < n; x++) {
      if ((x & 1) == 1)
        arr[x] = j--;
      else
        arr[x] = i++;
    }
 
    // Printing the array
    for (int x = (n - 1); x >= 0; x--) {
      Console.Write(arr[x] + " ");
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 10;
 
    // Function Call
    findPerm(N);
  }
}
 
// This code is contributed by phasing17

<script>
 // Javascript code to implement the above approach
  
// Function to print valid permutation of N
function findPerm(n)
{
 
    // Initialize the pointers
    let i = 1, j = n;
 
    // Declare an array of size N
   let arr=new Array(n);
 
    // Constructing the array
    for (let x = 0; x < n; x++) {
        if (x & 1)
            arr[x] = j--;
        else
            arr[x] = i++;
    }
 
    // Printing the array
    for (let x = (n - 1); x >= 0; x--) {
        document.write(arr[x] + " ");
    }
}
 
// Driver Code
    let N = 10;
 
    // Function Call
    findPerm(N);
     
    // This code is contributed by satwik4409.
    </script>

6 5 7 4 8 3 9 2 10 1 

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)