Создайте перестановку первых N натуральных чисел, имеющую количество уникальных смежных разностей, равное K

Даны два положительных целых числа N и K , задача состоит в том, чтобы построить такую перестановку первых N натуральных чисел, что все возможные абсолютные разности между соседними элементами равны K .

Примеры:

Input: N = 3, K = 1
Output: 1 2 3
Explanation: Considering the permutation {1, 2, 3}, all possible unique absolute difference of adjacent elements is {1}. Since the count is 1(= K), print the sequence {1, 2, 3} as the resultant permutation.

Input: N = 3, K = 2
Output: 1 3 2

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, используя подход с двумя указателями. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив ans[] размера N , в котором хранится результирующая перестановка.
• Создайте две переменные, скажем, левую и правую , как 1 и N соответственно .
• Пройдите по заданному массиву и выполните следующие шаги:
  • Если значение K четное, то поместите значение left в массив ans[] и увеличьте значение left на 1 .
  • Если значение K нечетное, нажмите значение правого в массив ans[] и уменьшите значение right на 1 .
  • Если значение K больше 1, затем уменьшите значение K на 1 .
• После выполнения вышеуказанных шагов напечатайте массив ans[] .

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

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