LC-0483 Hard LeetCode

483. Smallest Good Base

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 43% Topics: Math, Binary Search

Reading material

Math & Geometry 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(logn * log(logn))
# Space: O(1)

import math


class Solution(object):
    def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        num = int(n)
        max_len = int(math.log(num,2))
        for l in xrange(max_len, 1, -1):
            b = int(num ** (l**-1))
            if (b**(l+1)-1) // (b-1) == num:
                return str(b)
        return str(num-1)

Solution from kamyu104/LeetCode-Solutions · MIT