Минимальные операции для преобразования массива в перестановку от 1 до N путем замены остатком от некоторого d

Опубликовано: 20 Сентября, 2022

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти минимальное количество операций для преобразования массива в перестановку [1, n] , в каждой операции элемент a[i] может быть заменен на a[ i] % d , где d может быть разным для каждой выполняемой операции. Если это невозможно, выведите -1 .

Примеры:

Input: arr[] = {5, 4, 10, 8, 1}
Output: 2 
Explanation: In first operation choosing d = 7  , 10 can be replaced by 10 % 7  , 
In second operation d = 6, 8 can be replaced by 8 %6 so two operations.

Input : arr[] = {1, 2, 3, 7}
Output: -1

Подход: Задача может быть решена с использованием жадного подхода. Этот подход основан на том факте, что когда необходимо получить остаток r, то a[i] > 2*r , т.е. r лежит в диапазоне [0, a[i]-1/2]

Let us take an example: 8 for different d

Taking, 8 % 7= 1

           8%6 = 2

           8%5 = 3

          8%4 = 0

          8%3 = 2

          8%2 = 0

          8%1=0

So maximum number that can be obtained is 3 using mod operation, so when we want to obtain a number i in a permutation then the number should a[i] > 2* i+1

Выполните следующие действия, чтобы решить эту проблему:

  • Инициализировать набор s
  • Пройдите через массив arr[] и вставьте все элементы arr[] в набор.
  • Инициализировать переменную ops = 0
  • Теперь итерации от n до 1
  • Проверьте, есть ли у s уже i, если он удалил его из набора.
  • В противном случае увеличьте количество операций и проверьте, является ли наибольший элемент набора < 2* i +1
  • Если наибольший из множества меньше 2* i +1 , тогда установите ops = -1 и прервите цикл.
  • В противном случае сотрите его из набора, потому что мы можем сделать его с помощью операции мода.
  • Распечатать операции

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


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

РЕКОМЕНДУЕМЫЕ СТАТЬИ