Перестановка первых N элементов с абсолютной соседней разницей в порядке возрастания

По заданному натуральному числу N задача состоит в том, чтобы построить перестановку от 1 до N так, чтобы абсолютная разность элементов находилась в строго возрастающем порядке.

Примечание: N не может быть 0 или 1.

Примеры :

Input: N = 10
Output: 6 5 7 4 8 3 9 2 10 1
Explanation: abs(6 – 5) i.e., 1 < abs(5 – 7) i.e., 2 < abs(7 – 4) i.e., 3 …. < abs(2 – 10) i.e., 8 < abs(10 – 1) i.e., 9

Input: 3
Output: 2 3 1 
Explanation: abs(2 – 3) = 1 and abs(3 – 1) = 2, 1 < 2 hence it is in strictly increasing order.

Подход : Задача может быть решена на основе следующего наблюдения:

Наблюдение:

Let’s say, you have the i =1 and j = N, the largest absolute difference made is by subtracting 1 and N = (N – 1)

Next Time, i increment by 1, i = 2 and j remains same i.e., N, So, the absolute difference is = (N – 2).
Next Time, i remains same i.e., 2 and j decrement by 1, j = N-1, So, the absolute difference is = (N – 1 – 2) = (N – 3).
Next Time, i increment by 1, i = 3 and j remains same i.e., N-1, So, the absolute difference is = (N – 1 – 3) = (N – 4).
Next Time, i remains same i.e., 3 and j decrement by 1, j = N-2, So, the absolute difference is = (N – 2 – 3) = (N – 5)……

Now, this way the series go, and at last two condition possible,

• When i = j + 1, [If N is odd], absolute difference = 1
• Or, j = i + 1, [If N is even], absolute difference = 1

So, this way the series become for given N, series = (N – 1), (N – 2), (N – 3), …. 3, 2, 1.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте указатель i = 1 и j = N .
• Объявите массив размера N .
• Запустите цикл (используя итератор x ) от 0 до N-1 .
  • Если x четное, тогда устанавливается arr[x] = i и увеличивается i на 1 .
  • В противном случае установите arr[x] = j и уменьшите j на 1 .
• После выполнения цикла выведите массив в обратном порядке.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(N)