# C++ 3ms solution with explanation (no math derivation)

• It is obviously the base `b` must meets `n = b^k + b^(k-1) + ... + 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: bottom-up and top-down.

• For bottom-up: we set a `LIMIT` for `k`, as long as `b^k + b^(k-1) + ... + b^1 + 1 > n`, any larger number will not be able to form n with at least `k+1` parts, in other word with b^k included. So, we are done.

• For top-down: According to bottom-up result, just try from `LIMIT-1` to `2`.

If both ways not able to find a valid base, then the answer is `n-1` because `(n-1)^1 + 1 = n`.

The value of `LIMIT` is used to balance the number of repeats between top-down and bottom-up 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)) {
}
}

for (int j = LIMIT-1; j > 1; j--) {
long base = pow(num, 1.0/j);
if (base < 2) continue;
if (sum(base, j) == num) {
}
}
}

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;
}
};
``````

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