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

Дан массив arr[] . Задача состоит в том, чтобы минимизировать количество требуемых свопов, чтобы для каждого i в arr[] было arr[i]%3 = i%3 . Если такая перестановка невозможна, выведите -1.

Примеры:

Input: arr[ ] = {4, 3, 5, 2, 9, 7}
Output: 3
Explanation: Following are the operations performed in arr[]
Initially, index % 3 = {0, 1, 2, 0, 1, 2} and arr[i] % 3 = {1, 0, 2, 2, 0, 1}.
swap arr[0] and arr[1] updates arr[] to arr[]  % 3 = {0, 1, 2, 2, 0, 1}
swap arr[3] and arr[4] updates arr[] to arr[] % 3 = {0, 1, 2, 0, 2, 1}
swap arr[4] and arr[5] updates arr[] to arr[] % 3 = {0, 1, 2, 0, 1, 2}
Therefore, 3 swaps are required to get the resultant array which is minimum possible. 

Input: arr[] = {0, 1, 2, 3, 4}
Output: 0

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

• Перебрать массив с i от i = 0 до i=n-1
  • если arr[i] % 3 равно 0 , то продолжаем.
  • иначе найдите индекс j от i+1 до n-1 , где i % 3 = arr[j] % 3 и j % 3 = arr[i] % 3 .
  • С помощью вышеуказанного шага переместите два элемента массива в нужные позиции.
  • Если такого j не найдено, то найдите индекс k от i+1 до n-1 , где i % 3 = arr[k] % 3 , и поменяйте местами элементы.
  • Базовым случаем будет подсчет таких индексов, что index%3 = arr[i] % 3 .
• Верните окончательный счет в качестве требуемого ответа.

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

Временная сложность: O(N ² ), где N — размер arr[].

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