1
class Solution {
2
 public:
3
  string smallestGoodBase(string n) {
4
    string ans;
5
    long long nn = stol(n);
6

7
    // since n<1E18, the largest possible number of digits is 62.
8
    for (int i = 62; i > 2; i--) {
9
      // Since n = k^i-1 + k^i-2 + ... + k + 1, a good estimate of k is pow(n,
10
      // 1/(i-1))
11
      long long k = pow(nn, 1.0 / (i - 1));
12
      if (k == 1) continue;
13

14
      long long sum = 1, kk = 1;
15

16
      // Calculate the sum of i-ones base k. Although we have a direct approach
17
      // using the formula of geometric series sum, n = (k^i - 1)/(k-1), but
18
      // this approach has two issues: 1) k^i may be larger than LONG_MAX; 2)
19
      // the pow() function returns a float number which only has 15 decimal
20
      // digits precision, and not suitable for calculation of 18 digit int.
21
      for (int j = 1; j < i; j++) {
22
        kk *= k;
23
        sum += kk;
24
      }
25

26
      if (sum == nn) return to_string(k);
27
    }
28

29
    // We always have a trivial solution n-1. The number is 2 digits base (n-1);
30
    return to_string(nn - 1);
31
  }
32
};