Количество элементов массива, которые необходимо удалить, чтобы сделать абсолютную разницу между каждой парой одинаковой

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

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

Примеры:

Input: arr[] = {1, 2}
Output: 0
Explanation: There is only one pair of integers with absolute difference | arr[1] − arr[2] | = | 1- 2 | = 1. So there is no need to delete any integer from the given array.

Input: arr[] = {2, 5, 1, 2, 2}
Output: 2
Explanation: After deleting 1 and 5, the array A becomes [2, 2, 2] and the absolute difference between each pair of integers is 0.

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

  • Если максимальная частота среди всех элементов массива равна 1 , то необходимо удалить все (N – 2) элемента .
  • В противном случае максимальное количество элементов массива, которое необходимо удалить, равно (N — максимальная частота) , так что все элементы массива одинаковы, а разница между любыми двумя парами элементов одинакова.

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

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

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