# 5-liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation)

• Key Observation: if `N` in base `k >= 2` has all digits as `1`'s, that means `n` has representation

• `n =` Σp=0:d-1 `k`p,

where `d` is the number of digits in base `k`. So the problem is equivalent to

• find smallest `k >= 2` such that function `f(k,d)` := Σp=0:d-1 `k`p - `N` = `0` for some integer `d`.

As many fellow coders have posted the popular binary search solution for root of `f(*, d)` with some fixed `d`, but I think the search bound for `d` and `k` should be tightened as much as possible to speed up the algorithm.

Range of d: Note that `f(k,d)` is strictly increasing in `k`, which means `f(*,d)` has most one root for a fixed `d`.
Note that `f` can be rewritten as

• `f(k,d)` = (`k`d`-1`)/(`k-1`)`-N``f(2,d)` = `2`d`-1-N`,

so we must have `d``log2(N+1)` to be able to have a root for `f(*,d)`.

Range of k: for a fixed `d`, we have

• `f(k,d)` = (`k`d`-1`)/(`k-1`)`-N` < `k`d`-N`,

so we must have the root `k` > `N`1/d.
We also have

• `f(k,d)` = Σp=0:d-1 `k`p - `N` > `k`d-1`-N`,

so we must have the root `k` < `N`1/(d-1).

Summary: we loop `d` only in range `[2, log2(N+1)]` reversely, and for each `d`, we binary search root for `f(*,d)` only in range `[N`1/d, `N`1/(d-1)`]`.

``````    int64_t N; // =stoll(n)

string smallestGoodBase(string n) {
}

int64_t f(int64_t k, int64_t d) { // f(k,d) = sum k^i - N
for (int64_t i=0, p=1, sum=1; i<d; sum += p*=k) if (++i == d) return sum-N;
}

int64_t root(int64_t d) { // binary search root for f(*,d) in range [N^1/d, N^1/(d-1)]
int64_t m, v, L = pow(N, 1./d), R = pow(N, 1./(d-1));
for (; L <= R; v<0? L = m+1 : R = m-1) if (!(v = f(m=(L+R)/2,d))) return m;
return d>2? 0 : N-1;
}
``````

Time Complexity:

• The loop in `smallestGoodBase` has length `log N`.
• Apparently, function `f(k,d)` has `O(d)` complexity.
• In binary search `root`, we have `O(d*log(R-L)) = O(d*log R) = O(d*log N`1/(d-1)`) = O(log N)`.

So the overall time complexity is `O(log N)`2. (`N = stoll(n)`)

Improvement for Function `root`:
Actually, as @StefanPochmann pointed out in this post with binomial theorem, only `int64_t k = pow(N, 1./(d-1))` could be the candidate for the root of `f(*,d)`. So method `root` can be simplified as following:

``````    int64_t root(int64_t d) { // only N^1/(d-1) could be root for f(*,d)
int64_t k;
return d>2? f(k = pow(N,1./(d-1)), d)? 0 : k : N-1;
}
``````

The overall time complexity still stands as `O((log N)^2)`.

• @zzg_zzm Note that I was trying to use solver from Problem 50. Pow(x, n) in `f(k,d)` to achieve `O(log d)` complexity instead of the current `O(d)` complexity, but that involves calculation of `k^d` instead of `k^(d-1)`, and didn't work probably due to overflow of `int64_t`. Anyway, `d` is within `O(log N)` and this probably won't make much difference.

• This post is deleted!

• @zzg_zzm Very neat solution and nice explanation. Thank you!

• It's 5 lines, but take other 50x times to read your code. readability is very important.

string smallestGoodBase(string n) {
}

``````int64_t f(int64_t k, int64_t d) { // f(k,d) = sum k^i - N
for (int64_t i=0, p=1, sum=1; i<d; sum += p*=k) if (++i == d) return sum-N;
}

int64_t root(int64_t d) { // binary search root for f(*,d) in range [N^1/d, N^1/(d-1)]
int64_t m, v, L = pow(N, 1./d), R = pow(N, 1./(d-1));
for (; L <= R; v<0? L = m+1 : R = m-1) if (!(v = f(m=(L+R)/2,d))) return m;
return d>2? 0 : N-1;
}``````

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