Найдите перестановку [1, N] такую, что (arr[i] != i+1) и сумма абсолютной разницы между arr[i] и (i+1) минимальна

Для заданного положительного целого числа N задача состоит в том, чтобы найти перестановку первых N натуральных чисел, скажем, arr[] такую, что (arr[i] != i + 1) , и сумму абсолютной разницы между arr[i] и (i + 1) минимально .

Примеры:

Input: N = 4
Output: 2 1 4 3
Explanation:
Consider the permutation {2, 1, 4, 3}, Now, the sum is abs(2 – 1) + abs(1 – 2) + abs(4 – 3) + abs(3 – 4) = 1 + 1 + 1 + 1 = 4, which is minimum.

Input: N = 7
Output: 2 1 4 3 6 7 5

Наивный подход: самый простой подход к решению данной проблемы — сгенерировать все возможные перестановки первых N натуральных чисел и напечатать ту перестановку, которая удовлетворяет заданным критериям.

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

Эффективный подход. Описанный выше подход также можно оптимизировать, заметив тот факт, что результирующий массив может быть сформирован путем перестановки чередующихся соседних пар, чтобы обеспечить новую позицию с минимальной суммой абсолютной разницы между arr[i] и (i + 1) . В случае, когда N больше 1 и N нечетно, последний элемент может быть заменен любым предпоследним или третьим последним элементом перестановки. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте массив, скажем, arr[] первыми N натуральными числами, расположенными в порядке возрастания.
• Пройдитесь по массиву и поменяйте местами все соседние элементы как swap ( arr[i], arr[i – 1]) .
• Теперь, если значение N больше 1 и N нечетно, тогда swap(arr[N – 1], arr[N – 2]) .
• После выполнения вышеуказанных шагов выведите массив arr[] в качестве результирующей перестановки.

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

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