Найдите диапазон значений для S в заданном массиве со значениями, удовлетворяющими [ arr[i] = floor((i*S)/K) ]

Учитывая массив arr[] из N положительных целых чисел и положительное целое число K , задача состоит в том, чтобы найти диапазон [L, R] такой, что для всех элементов в этом диапазоне, скажем S , каждый элемент массива arr[i] равен полу( (i*S)/К) .

Примеры:

Input: N = 5, K = 10, arr[] = {2, 4, 6, 9, 11}
Output: 23 23
Explanation: 
When S = 23, substituting in the equation gives the same array values:
arr[1] = floor((1*23)/10) = 2
arr[2] = floor((2*23/10)) = 4
arr[3] = floor((3*23/10)) = 6
arr[4] = floor((4*23/10)) = 9
arr[5] = floor((5*23/10)) = 11

Input: N = 5, K = 100, arr[] = {0, 0, 0, 0, 1}
Output: 20 24

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

• Инициализируйте две переменные, скажем, L и R как INT_MIN и INT_MAX, которые хранят значение левого диапазона и правого диапазона соответственно.
• Пройдите по заданному массиву arr[] и выполните следующие шаги:
  • Найдите возможное значение левого диапазона для i ^-го элемента массива как ceil(1.0*arr[i]*K/(i + 1)) .
  • Найдите возможное значение правильного диапазона для i ^-го элемента массива как ceil((1.0 + arr[i])*K/(i + 1)) – 1 .
  • Обновите значение L как max(L, l) и значение R как min(R, r) .
• После выполнения вышеуказанных шагов выведите значения L и R в качестве результирующего диапазона.

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

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