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)