Минимум операций, необходимых для уменьшения N до 0 путем замены N на N/M или увеличения M на 1.

Даны два целых числа N и M , задача состоит в том, чтобы вычислить минимальное количество операций, необходимых для уменьшения N до 0 , используя следующие операции:

• Замените N на (N/M) .
• Увеличьте значение M на 1 .

Пример:

Input: N = 9, M = 2
Output: 4
Explanation: The given example can be solved by following the below sequence of operations:

• In 1st operation, replace N with (N/M), i.e, N = 9/2 = 4.
• In 2nd operation, again replace N with N/M, i.e, N = 4/2 = 2.
• In 3rd operation, increment M by 1, i.e, M = M+1 = 2+1 = 3.
• In 4th operation, replace N with N/M, i.e, N = 2/3 = 0.

Hence, the number of required operations is 4 which is the minimum possible.

Input: N = 15, M = 1
Output: 5

Подход: Данную проблему можно решить, заметив тот факт, что наиболее оптимальным выбором операций является увеличение значения M , скажем, в x раз, а затем уменьшение значения N до N/(M+x) , пока оно не станет равным 0 . Чтобы найти наилучший случай, выполните итерацию по всем значениям x в диапазоне [0, √N], используя переменную i , и рассчитайте количество шагов, необходимых для уменьшения N до 0 , разделив его на (M+i). Следите за минимальным количеством операций над всеми возможными значениями (M+i) в переменной ans , что является требуемым значением.

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

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