Минимизируйте максимальный элемент массива, разделив элементы массива на степени двойки не более K раз

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

Примеры:

Input: arr[] = {2, 4, 11, 2}, K = 2
Output: 2
Explanation:
Below are the operations performed on array elements at most K(= 2) times:
Operation 1: Remove the element at index 2, i.e., arr[2] = 11 and replace it with 11 numbers of 1s in it. Now the array arr[] modifies to {2, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}.
Operation 2: Remove the element at index 1, i.e., arr[1] = 4 and replace it with 4 numbers of 1s in it. Now the array arr[] modifies to {2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}.

After performing the above operations, the maximum value of the array is 2, which is minimum possible value.

Input: arr[]= {9}, K = 2
Output: 1

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

• Отсортируйте массив arr[] по убыванию.
• Найдите количество нулей в массиве arr[], если значение count равно N , затем выведите 0 как результирующее минимальное максимальное значение массива.
• В противном случае, если значение K не меньше N , выведите 1 как результирующее минимальное максимальное значение массива.
• В противном случае выведите значение arr[K] как результирующее минимальное максимальное значение массива.

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

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

Еще один эффективный подход: в предыдущем подходе мы сортировали массив и находили (K+1)-й максимальный элемент для K<N. Вместо сортировки массива мы можем использовать приоритетную очередь , чтобы найти (K+1)-й максимальный элемент.

Временная сложность для этого подхода в худшем случае составляет O(N*log(K)) для k<N, в противном случае временная сложность составляет O(1). Следовательно, данный подход намного лучше предыдущего для меньшего значения k.

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

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