Минимизируйте свопы, чтобы сделать остаток равным, когда элемент и его индекс делятся на K

Учитывая массив arr[] положительных целых чисел и положительное число K, задача состоит в том, чтобы найти минимальные требуемые перестановки элементов, чтобы для каждого элемента с индексом i выполнялось следующее условие:

 arr[i] % K =  i % K 

Пример:

Input: arr = {4, 3, 5, 2, 9, 7}, K=3
Output: 3
Explanation: Index % 3 = 0 1 2 0 1 2 and arr[i] % 3 = 1 0 2 2 0 1
swap index 0 with index 1 => 0 1 2 2 0 1
swap index 3 with index 4 => 0 1 2 0 2 1
swap index 4 with index 5 => 1 0 2 0 1 2

Input: arr = {0, 1, 2, 3, 4, 5}, K=1
Output: 0

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

• Проверить, можно ли выполнить задание, сравнив частоты индекса %k с элементом %k
  • Если частоты не совпадают, возвращаем -1
• Итерировать массив и по каждому индексу i :
  • Если arr[i] % 3 == i % 3 , то переходите к следующему индексу
  • В противном случае, если arr[i] % 3 != i % 3 , тогда найдите индекс j от i+1 до N-1, где i % 3 = arr[j] % 3 и j % 3 = arr[i] % 3 , что приведет два элемента в их точные положения
  • В противном случае найдите индекс k, перебирая от i+1 до N-1, где i % 3 = arr[k] % 3, и поменяйте местами элементы

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

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