# 483. Smallest Good Base

• Time: $O(\log^2n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: string smallestGoodBase(string n) { const long num = stol(n); for (int m = log2(num); m >= 2; --m) { const int k = pow(num, 1.0 / m); long sum = 1; long prod = 1; for (int i = 0; i < m; ++i) { prod *= k; sum += prod; } if (sum == num) return to_string(k); } return to_string(num - 1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public String smallestGoodBase(String n) { final long num = Long.parseLong(n); final int log2 = (int) (Math.log(num) / Math.log(2)); for (int m = log2; m >= 2; --m) { int k = (int) Math.floor(Math.pow(num, 1.0 / m)); long sum = 1; long prod = 1; for (int i = 0; i < m; ++i) { prod *= k; sum += prod; } if (sum == num) return String.valueOf(k); } return String.valueOf(num - 1); } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def smallestGoodBase(self, n: str) -> str: n = int(n) for m in range(int(math.log(n, 2)), 1, -1): k = int(n**m**-1) if (k**(m + 1) - 1) // (k - 1) == n: return str(k) return str(n - 1)