Accepted Solution in Python


  • 1
    A

    Technique Used : Binary Search
    Complexity : k*log(n)

    The Method :

    When all the characters are '1' for a base b then n should be of the form
    (b^x -1)/(b-1) for some x ,
    given a power x and n , we could use binary search to see if we could bring n in that form
    for any base b , as it is a monotonic function.
    So all we have to do is for each power x from 2 to 70 , to see if we could find a base b.

    from math import log
    class Solution(object):
        def tryout(self,n,k):
            l = 2
            r = n
            while(l<=r):
                m = (l+r)/2
                x  = pow(m,k)-1
                x/=(m-1)
                if(x == n):
                    return m
                elif(x>n):
                    r = m-1
                else:
                    l = m+1
            return n-1
        def smallestGoodBase(self, n):
            """
            :type n: str
            :rtype: str
            """
            n = int(n)
            ans = n-1
            for i in xrange(2,71):
                ans = min(ans,self.tryout(n,i))
            return str(ans)
            
    

Log in to reply
 

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