Минимальное количество элементов массива, которые необходимо изменить так, чтобы разница между максимальным и минимальным элементом массива составляла N – 1.

Для заданного массива arr[] , состоящего из N целых чисел, задача состоит в том, чтобы найти минимальное количество элементов массива, которое необходимо заменить любыми произвольными целыми числами так, чтобы разница между максимальным и минимальным элементом массива была (N – 1) и всеми элементами массива должны быть различимы.

Примеры:

Input: arr[] = {1, 2, 3, 5, 6}
Output: 1
Explanation:
Change 6->4, the final array will be {1, 2, 3, 5, 4} and the difference is equal to 5 – 1 = 4.

Input: arr[] = {1, 10, 100, 1000}
Output: 3

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

• Отсортируйте массив в порядке неубывания.
• Сохраните переменную ans и инициализируйте ее значением N , которое будет хранить минимально возможный ответ.
• Удалить все повторяющиеся элементы из заданного массива arr[].
• Перебрать диапазон [0, M), где M — новый размер массива после удаления дубликатов с помощью переменной i , и выполнить следующие задачи:
  • Пройдите в цикле while до тех пор, пока j не станет меньше M , а A[j] меньше, чем A[i] + N – 1 , и увеличьте значение j на 1 .
  • Обновите значение ans до минимума ans и (N – j + i) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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