It is obviously the base b
must meets n = b^k + b^(k1) + ... + b^1 + 1
The straightforward way is to try from 2
to n
, once it meets the formula above, we are done. But it will get TLE. To minimize the number of candidates, we do it from both directions: bottomup and topdown.

For bottomup: we set a
LIMIT
fork
, as long asb^k + b^(k1) + ... + b^1 + 1 > n
, any larger number will not be able to form n with at leastk+1
parts, in other word with b^k included. So, we are done. 
For topdown: According to bottomup result, just try from
LIMIT1
to2
.
If both ways not able to find a valid base, then the answer is n1
because (n1)^1 + 1 = n
.
The value of LIMIT
is used to balance the number of repeats between topdown and bottomup loops
#define LIMIT 8
class Solution {
public:
string smallestGoodBase(string n) {
long num = stol(n);
for (int base = 2; sum(base, LIMIT) <= num; base++) {
if (valid(num, base)) {
return to_string(base);
}
}
for (int j = LIMIT1; j > 1; j) {
long base = pow(num, 1.0/j);
if (base < 2) continue;
if (sum(base, j) == num) {
return to_string(base);
}
}
return to_string(num1);
}
bool valid(long n, int base) {
while(n) {
if (n % base != 1) return false;
n /= base;
}
return true;
}
long sum(int base, int k) {
long res = 1;
long num = 1;
for (int i = 0; i < k; i++) {
num *= base;
res += num;
}
return res;
}
};