Наименьшее возможное целое число K такое, что ceil каждого элемента массива при делении на K не превышает M

Дан массив arr[] , состоящий из N положительных целых чисел и положительного целого числа M , задача состоит в том, чтобы найти наименьшее возможное целое число K такое, что ceil(arr[0]/K) + ceil(arr[1]/K) +… .+ ceil(arr[N – 1]/K) не превосходит M .

Примеры:

Input: arr[] = {4, 3, 2, 7}, M = 5
Output: 4
Explanation:
For K = 4,  the value of ceil(4/4) + ceil(3/4) + ceil(2/4) + ceil(7/4) = 1 + 1 + 1 + 2 = 5. Therefore, print 5.

Input: arr[] = {1, 2, 3}, M = 4
Output: 2

Подход: Идея заключается в использовании бинарного поиска. Установите нижнее значение как 1 , а высокое значение как максимальное значение из массива arr[] и найдите значение K , которое меньше или равно M , применяя двоичный поиск. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные, скажем, low = 1 и high как максимальный элемент массива.
• Повторите цикл while до высокого – низкого > 1 и выполните следующие задачи:
  • Обновите значение mid на mid = (low + high)/2 .
  • Пройдите массив arr[] и найдите сумму ceil(arr[i]/K) , приняв mid за K .
  • Если сумма больше М , то обновить значение high до high = mid . В противном случае обновите значение low до low = mid + 1 .
• После выполнения вышеуказанных шагов выведите значение low , если сумма не превышает M. В противном случае выведите значение high .

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

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