Найдите перестановку N чисел в диапазоне [1, N] так, чтобы K чисел имели значение, такое же, как их индекс

Даны положительное целое число N и целое число K , такое что 0 ≤ K ≤ N , задача состоит в том, чтобы найти любую перестановку A из [1, N] такую, что количество индексов, для которых A _i = i , равно точно K ( основанному на 1 индексация ). Если такой перестановки не существует, выведите −1 .

Примеры:

Input: N = 3, K = 1
Output: 1 3 2
Explanation: Consider the permutation A = [1, 3, 2]. We have A1=1, A2=3 and A3=2. 
So, this permutation has exactly 1 index such that A_i = i.

Input: N = 2, K = 1
Output: -1
Explanation : There are total 2 permutations of [1, 2] which are [1, 2] and [2, 1]. 
There are 2 indices in [1, 2] and 0 indices in [2, 1] for which A_i = i holds true. 
Thus, there doesn’t exist any permutation of [1, 2] with exactly 1 index i for which Ai=i holds true.

Подход: Задача может быть решена с использованием жадного подхода. Сначала зафиксируйте ровно K элементов по их индексам, а затем просто случайным образом разместите NK элементов в разных местах. Выполните следующие шаги, чтобы решить проблему:

1. Как-то исправить K позиций
2. Переместить оставшиеся номера NK
3. Циклический сдвиг оставшегося элемента на единицу

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

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