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)
```