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

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

Примеры:

Input: arr[] = {1, 3, 2, 2}, K = 2
Output: 3
Explanation:
Below are the operations performed:

1. Add 1 to the element at index 2(= 2), then the array modifies to {1, 3, 3, 2}.
2. Add 1 to the element at index 3(= 2), then the array modifies to {1, 3, 3, 3}.

After the above steps, the maximum frequency of an array element is 3.

Input: arr[] = {4, 3, 4}, K = 5
Output: 2

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

• Инициализируйте переменные, скажем, start , end , sum как 0 и mostFreq как INT_MIN.
• Отсортируйте массив arr[] по возрастанию.
• Переберите диапазон [0, N – 1], используя переменную end , и выполните следующие шаги:
  • Увеличьте значение sum на значение arr[end] .
  • Пока значение (sum + K) меньше значения (arr[end] * (end – start+ 1)) , затем уменьшите значение суммы на arr[start] и увеличьте значение start на 1 .
  • Обновите значение mostFreq до максимального значения mostFreq и (end – start + 1) .
• Инициализируйте переменную, скажем, reqSum как значение (arr[N-1] * N – sum) , в котором хранится результирующая сумма, чтобы сделать все элементы массива равными.
• Если значение mostFreq равно N , а значение K больше, чем reqSum , то уменьшается значение K на reqSum .
• Если значение K кратно N , то выведите N . В противном случае выведите значение (N – 1) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение mostFreq .

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

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