Python O(logN) Binary search on "111...111" solution


  • 1
    H
    class Solution(object):
        def smallestGoodBase(self, n):
            """
            :type n: str
            :rtype: str
            """
    
            n = int(n)
            max_len = len(bin(n)) - 2     # the longest possible representation "11111....1" based on k
            for m in range(max_len, 1, -1):
                lo = 2
                hi = n - 1     # or hi = int(pow(n, pow(m - 1, -1))) and only need check hi
                while lo <= hi:
                    mid = (lo + hi) / 2
                    num = (pow(mid, m) - 1) // (mid - 1)
                    if num < n:
                        lo = mid + 1
                    elif num > n:
                        hi = mid - 1
                    else:
                        return str(mid)
            return str(n - 1)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.