Минимизируйте значение a в ряду a, a/b^1, a/b^2, a/b^3,..., a/b^n так, чтобы сумма начальных ненулевых членов стала не менее S

Даны два целых числа b и S . Задача состоит в том, чтобы найти минимальное значение ' a ' такое, чтобы сумма стала равной или больше, чем ' S ' для начальных ненулевых членов.

a, a/b¹, a/b², a/b³, …………., a/bⁿ

Пример:

Input: b = 2, S = 4
Output: 3
Explanation: 

• Let a = 1, S = 1/2⁰ + 1/2¹ = 1 + 0 = 1 < 4.
• Let a =2, S = 2/2⁰ + 2/2¹ + 2/2² = 2 + 1 + 0 = 3 < 4.
• Let a = 3, S = 3/2⁰ + 3/2¹ + 3/2² = 3 + 1 + 0 = 4 = S.

So, a = 3 is the answer.

Input: b = 8, S = 25
Output: 23

Подход: Эта проблема может быть решена с помощью бинарного поиска, чтобы найти ответ. Очевидно, что если число ' a ' является ответом, то каждое число n > a также является ответом, потому что значений станет только больше, а нам нужно найти минимальное . Итак, для проверки некоторого числа «а» мы можем воспользоваться формулой, приведенной в самой задаче. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные a как 1, low как 0 и high как S.
• Пройдите в цикле while до тех пор, пока низкий уровень не станет меньше, чем высокий , и выполните следующие задачи:
  • Инициализируйте переменную mid как среднее значение low и high.
  • Инициализируйте x как b и суммируйте как mid.
  • Пройдите в цикле while до тех пор, пока значение mid/x не станет больше 0 , и выполните следующие задачи:
    • Добавьте значение mid/x к переменной sum .
    • Умножьте значение b на переменную x.
  • Если сумма больше, чем равна S , установите a как среднее , а high как среднее-1.
  • В противном случае установите низкий уровень как средний + 1.
• После выполнения вышеуказанных шагов выведите значение a в качестве ответа.

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

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