Problem statement

https://leetcode.com/problems/smallest-good-base/

Solution

We are actually asked to find the smallest a such that for some natural k: 1 + a + ... + a^k = n. It is equivalent to finding the maximum k, which is less than log_2(n). So, we start with k equal to integer part of log_2(n) and decrease it and try to solve equation of a: 1 + a + ... + a^k = n. We can solve this equation either using binary search or we can note, that a < n^{1/k} < a+1 for k >= 2, so the only candidate we have for a is [n^{1/k}] (and we need to handle case k = 1 separately).

Complexity

Time complexity is O(log n), space is O(1).

Code

class Solution(object):
    def smallestGoodBase(self, n):
        n = int(n)
        max_k = int(log(n, 2))
        for k in range(max_k,1,-1):
            a = int(n**(1/k))
            if (a**(k + 1) - 1)//(a - 1) == n:
                return str(a)
        return str(n - 1)