# Python solution with detailed mathematical explanation and derivation

• 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) ...... [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 ...... [2]

from [1] and [2],

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 .... [3]

Also from [1] 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 .... [4]

[EDIT] -->

With inputs from @StefanPochmann we can also say, from binomial thorem, n = k^m + ... + 1 < (k+1)^m .... [5]
Therefore, k+1 > m-th root of n > k. .... from [4] and [5]
Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. [6]

<--

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 [6] 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) [7]

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 [7]
for m in range(max_m,1,-1):
k = int(n**m**-1)  # Refer [6]
if (k**(m+1)-1)//(k-1) == n:
# Refer [3]
return str(k)

return str(n-1)
``````

<—-

• Nice explanation. 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.

So k < m-th root of n < k+1. Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. As @hausch did here.

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 had a proof to get a lower bound as (m+1)st root of n in my post. I thought it was tight enough, but... :-(

• @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

• @rtmatx
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.

• This post is deleted!

• @zhongyuan9817 Thanks @zhongyuan9817 I understood the logic. I am not thinking in the correct way!

• @StefanPochmann Thanks a lot. Your new explanation cleared all my doubts. I am sorry if it took you lot of time :(

• @StefanPochmann
Can the same logic be written in C++ code ?

• @StefanPochmann
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)?

• @livelearn
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) [7]", right?

• Nice explanation, here is java version

``````import java.math.*;
class Solution {
public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
BigInteger bn = BigInteger.valueOf(num);
int max_m = (int) (Math.log(num) / Math.log(2));
for (int m = max_m; m >= 1; m--) {
BigInteger k = BigInteger.valueOf((long) Math.floor(Math.pow(num, 1.0 / m)));
BigInteger left = k.pow(m + 1).subtract(BigInteger.ONE);
BigInteger right = bn.multiply(k.subtract(BigInteger.ONE));
if (left.equals(right)) {
return String.valueOf(k);
}
}
return String.valueOf(num - 1);
}
}
``````

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