First things first. Let's see the math behind it.
From given information, we can say one thing- Numbers will be of form-
n = k^m + k^(m-1) + ... + k + 1
=> n-1 = k^m + k^(m-1) + ... + k
=> n-1 = k (k^(m-1) + k^(m-2) + ... + k + 1) ...... 
Also, from n = k^m + k^(m-1) + ... + k + 1, we can say,
n-k^m = k^(m-1) + k^(m-2) + ... + k + 1 ...... 
from  and ,
n-1 = k (n - k^m)
=>k^(m+1) = nk - n + 1
if you shuffle sides you will end up getting following form,
(k^(m+1) - 1)/(k - 1) = n .... 
Also from  note that, (n - 1) must be divisible by k.
We know that, n = k^m + k^(m-1) + ... + k + 1
=> n > k^m
=> m-th root of n > k .... 
With inputs from @StefanPochmann we can also say, from binomial thorem, n = k^m + ... + 1 < (k+1)^m .... 
Therefore, k+1 > m-th root of n > k. .... from  and 
Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. 
So our number should satisfy this equation where k will be our base and m will be (number of 1s - 1)
This brings us to the search problem where we need to find k and m.
Linear search from 1 to n does not work. it gives us TLE. So it leaves us with performing some optimization on search space.
From  we know that the only candidate that needs to be tested is, ⌊m-th root of n⌋
We also know that the smallest base is 2 so we can find our m must be between 2 and log2n else m is (n-1) 
That brings me to the code:
[EDIT] -- >
import math class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ n = int(n) max_m = int(math.log(n,2)) # Refer  for m in range(max_m,1,-1): k = int(n**m**-1) # Refer  if (k**(m+1)-1)//(k-1) == n: # Refer  return str(k) return str(n-1)
Two little mistakes: (not anymore, after the edit) You fail n = "3", returning "1". 10^18 < 2^55 is false. But it doesn't seem to matter?
For a given m > 1:
From n = km + ... + k0 > km you get k < m-th root of n (as you said already).
From n = km + ... + k0 < (k+1)m (see binomial theorem) you also get k+1 > m-th root of n.
Edit: More explanations:
I think of the above k < x < k+1 (with x being the m-th root of n) as x being really close to the potentially existing k. Rounding it down might be a working k, but integers larger than that can't be (because already x is larger than k) and integers smaller also can't be (because x < k+1 shows that x is less than 1 too large, so if we subtract 1 or more, we'd be too small).
You can also reverse the focus, though, and turn those inequations into x-1 < k < x. In other words, k would have to be an integer between x-1 and x. So round down x to get the only integer in that little range. Yeah ok, this is probably the easier viewpoint :-)
And to show km + ... + k0 < (k+1)m: One way to see it is that expanding (k+1)m gives you all those powers of k, most of them multiple times, for example (k+1)4 = k4+4k3+6k2+4k1+k0. The binomial theorem just makes that more formal, giving us (k+1)m = ∑i=0:m (m choose i)⋅ki. Here (m choose i) is at least 1, and larger than 1 when i is strictly between 0 and m (this is btw where "m > 1" comes into play, guaranteeing such an i). So we have (k+1)m = ∑i=0:m (m choose i)⋅ki > ∑i=0:m ki.
@StefanPochmann nice proof!
@StefanPochmann Thanks for your inputs! I will take that in account.
@harshaneel Did you accidentally remove your derivation of "m-th root of n > k"? I don't see it anymore, but I think I got that part from you.
@StefanPochmann Yeah I accidentally removed it. Added it again with some more comments and references.
@StefanPochmann I didn't understand why the floor of m-th root of n has to be the only candidate for k.
k < m-th root of n < k+1. I can only understand that m-th root of n will be a float because k is always a positive number. Also, won't the floor of m-th root on n be k and not more than it ?
Sorry if I asked a stupid question
k < m-th root of n < k+1
2 < x < 3
x must be 2.xxxxx
floor(x) just round this float number to the largest previous integer, so it must equal to integer 2, how could it be more than 2?
@rtmatx I added some more explanations, have a look again.
@StefanPochmann Thanks a lot. Your new explanation cleared all my doubts. I am sorry if it took you lot of time :(
Can the same logic be written in C++ code ?
Can the same logic be written in C++ code ?
I have a post in C++ with basically the same logic if you are interested:
10-liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation)
@StefanPochmann Can you prove that that the smallest base is between 2 and log2n else m is (n-1)?
We know n > k^m. Since k>=2, we can get m<=log2(n). We know n is an non-negative integer. Here, the input n is between [3, 10^18]. Therefore, m cannot be zero, in which case n=1. When m=1, the base k is (n-1), because (n-1)^1+(n-1)^0=n. Here, (n-1) is always a good base.
@harshaneel I think you mean "else base k is (n-1) ", right?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.