Smallest Good Base Problem

Problem

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1's.

Examples

Example 1:

Input: n = "13" Output: "3" Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681" Output: "8" Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000" Output: "999999999999999999" Explanation: 1000000000000000000 base 999999999999999999 is 11.

Solution

Method 1 – Binary Search for Base Length

Intuition

A number n can be written as 1 + k + k^2 + ... + k^m for some base k and integer m ≥ 1. For each possible m (from max to 1), we can binary search for k such that this sum equals n. The smallest k > 1 found is the answer.

Approach

1. For m from max possible (log2(n)) down to 1:
   • Use binary search to find k in [2, n^(1/m)+1] such that 1 + k + ... + k^m == n.
   • If found, return k as string.
2. If no such k found, return n-1 (since n = 1 + (n-1)).

Code

Java

class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        for (int m = (int)(Math.log(num) / Math.log(2)); m >= 1; m--) {
            long l = 2, r = (long)Math.pow(num, 1.0/m) + 1;
            while (l <= r) {
                long k = l + (r-l)/2, sum = 1, cur = 1;
                for (int i = 1; i <= m; i++) {
                    cur *= k;
                    sum += cur;
                }
                if (sum == num) return String.valueOf(k);
                if (sum < num) l = k+1;
                else r = k-1;
            }
        }
        return String.valueOf(num-1);
    }
}

Python

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        num = int(n)
        for m in range(num.bit_length(), 1, -1):
            l, r = 2, int(num ** (1/(m-1))) + 1
            while l <= r:
                k = (l + r) // 2
                s, cur = 1, 1
                for _ in range(1, m):
                    cur *= k
                    s += cur
                if s == num:
                    return str(k)
                if s < num:
                    l = k + 1
                else:
                    r = k - 1
        return str(num - 1)

Complexity

• ⏰ Time complexity: O((log n)^2), since for each m (up to log n), we binary search for k (up to log n steps), and each check is O(log n).
• 🧺 Space complexity: O(1), only constant extra space is used.

Method 2 - Mathematical Formula

Intuition

For each possible length m, we can try to solve the equation n = (k^{m+1} - 1) / (k - 1) for integer k > 1. If k is integer and the sum matches n, return k.

Approach

1. For m from max possible (log2(n)) down to 1:
   • Compute k = int(n ** (1/m)).
   • If (k^m+1 - 1) // (k - 1) == n, return k.
2. If no such k found, return n-1.

Code

Java

class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        for (int m = (int)(Math.log(num) / Math.log(2)); m >= 1; m--) {
            long k = (long)Math.pow(num, 1.0/m);
            long sum = 1, cur = 1;
            for (int i = 1; i <= m; i++) {
                cur *= k;
                sum += cur;
            }
            if (sum == num) return String.valueOf(k);
        }
        return String.valueOf(num-1);
    }
}

Python

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        num = int(n)
        for m in range(num.bit_length(), 1, -1):
            k = int(num ** (1/(m-1)))
            s, cur = 1, 1
            for _ in range(1, m):
                cur *= k
                s += cur
            if s == num:
                return str(k)
        return str(num - 1)

Complexity

• ⏰ Time complexity: O((log n)^2), for each m (up to log n), we try a candidate k and check the sum in O(log n).
• 🧺 Space complexity: O(1), only constant extra space is used.