LeetCode 483 - Smallest Good Base

The problem is asking us to find the smallest integer k = 2 such that a given number n can be represented in base k with all digits equal to 1. In other words, we want n to be a sum of consecutive powers of k, like 1 + k + k^2 + ... + k^(m-1) for some integer m = 2.

leetcodehardmathbinary-search

LeetCode Problem 483

Difficulty: 🔴 Hard
Topics: Math, Binary Search

Solution

Problem Understanding

The problem is asking us to find the smallest integer k >= 2 such that a given number n can be represented in base k with all digits equal to 1. In other words, we want n to be a sum of consecutive powers of k, like 1 + k + k^2 + ... + k^(m-1) for some integer m >= 2. The input n is given as a string because it can be very large, up to 10^18, which exceeds typical 32-bit or even 64-bit integer limits in some languages. The output is also expected as a string representing the smallest valid base.

Important aspects of the problem include understanding that n can be extremely large, so iterating over all possible bases naively will not work. Also, the sequence of digits being all 1s means we are looking for numbers of the form of a geometric series sum. Edge cases to consider are the smallest valid n (3), very large numbers near 10^18, and numbers that are powers of 2 or 3 which might have multiple valid bases.

Approaches

Brute Force

A naive brute-force approach would try every base k from 2 up to n-1, convert n to that base, and check if all digits are 1. While this guarantees a correct answer, it is extremely slow because n can be as large as 10^18. Checking all bases up to n-1 is clearly infeasible.

Optimal Approach

The key insight is that n represented in base k as all 1s can be written as a geometric series: n = 1 + k + k^2 + ... + k^(m-1) for some m >= 2. Using the formula for a geometric series, this becomes:

n = (k^m - 1) / (k - 1)

This equation allows us to reformulate the problem: for each possible m (number of 1's), find an integer k that satisfies the equation. The maximum possible length m occurs when k=2 because larger bases produce shorter sequences. Thus, m ranges from the floor of log2(n) down to 2. For each m, we can solve for k using binary search between 2 and n^(1/(m-1)).

This approach drastically reduces the search space, because instead of iterating over potentially 10^18 bases, we iterate over at most log2(n) sequence lengths and binary search over a smaller range for each.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(log n) Iterate all bases and check digits
Optimal O(log n * log n) O(1) Iterate possible lengths m and binary search k

Algorithm Walkthrough

  1. Convert the input string n to an integer.
  2. Compute the maximum possible length max_m of the sequence, which is floor(log2(n)) + 1.
  3. Loop over m from max_m down to 2.
  4. For each m, perform a binary search for k in the range [2, n^(1/(m-1))].
  5. For each candidate k, calculate the geometric series sum 1 + k + k^2 + ... + k^(m-1).
  6. If the sum equals n, return k as a string.
  7. If no k is found for any m, return n-1 as a string (since n in base n-1 is always 11).

Why it works: The loop ensures we try the longest sequences first, which will produce the smallest base. Binary search guarantees finding an integer k that satisfies the geometric series sum exactly, avoiding precision errors.

Python Solution

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n_int = int(n)
        max_m = n_int.bit_length()  # floor(log2(n)) + 1

        for m in range(max_m, 1, -1):
            left, right = 2, int(n_int ** (1 / (m - 1))) + 1
            while left <= right:
                k = (left + right) // 2
                # geometric sum: (k**m - 1) // (k - 1)
                sum_ = 1
                curr = 1
                for _ in range(m - 1):
                    curr *= k
                    sum_ += curr
                    if sum_ > n_int:
                        break
                if sum_ == n_int:
                    return str(k)
                elif sum_ < n_int:
                    left = k + 1
                else:
                    right = k - 1
        return str(n_int - 1)

The Python implementation first converts n to an integer and computes the maximum sequence length using the bit length of n. It iterates from longest to shortest possible sequences to prioritize smaller bases. For each sequence length, a binary search identifies the candidate base k. The geometric series sum is computed iteratively to avoid overflow, and the loop breaks early if the sum exceeds n. If no valid base is found, the default base is n-1.

Go Solution

import (
    "math"
    "strconv"
)

func smallestGoodBase(n string) string {
    nInt, _ := strconv.ParseInt(n, 10, 64)
    maxM := int(math.Log2(float64(nInt))) + 1

    for m := maxM; m >= 2; m-- {
        left, right := int64(2), int64(math.Pow(float64(nInt), 1.0/float64(m-1)))+1
        for left <= right {
            k := (left + right) / 2
            sum := int64(1)
            curr := int64(1)
            for i := 0; i < m-1; i++ {
                curr *= k
                sum += curr
                if sum > nInt {
                    break
                }
            }
            if sum == nInt {
                return strconv.FormatInt(k, 10)
            } else if sum < nInt {
                left = k + 1
            } else {
                right = k - 1
            }
        }
    }
    return strconv.FormatInt(nInt-1, 10)
}

In Go, strconv.ParseInt converts the string to an integer, and math.Log2 determines the maximum sequence length. The binary search iterates over candidate bases and computes the geometric series iteratively using int64 arithmetic. The result is returned as a string using strconv.FormatInt.

Worked Examples

Example 1: n = "13"

Step m left right k sum Notes
1 4 2 2 2 15 sum > n, move right
2 3 2 3 2 7 sum < n, move left
3 3 3 3 3 13 sum == n, return 3

Example 2: n = "4681"

Step m left right k sum Notes
... 5 2 8 8 4681 sum == n, return 8

Example 3: n = "1000000000000000000"

Step m left right k sum Notes
... 2 2 999999999999999999 999999999999999999 1000000000000000000 sum == n, return 999999999999999999

Complexity Analysis

Measure Complexity Explanation
Time O(log n * log n) Outer loop over m is O(log n), binary search for k is O(log n)
Space O(1) Only a few integers are stored, no extra data structures

Iterating over sequence lengths and performing binary search for each candidate base ensures the algorithm scales efficiently, even for n near 10^18. Iterative computation of the geometric sum avoids large power computations that could overflow.

Test Cases

# Basic examples
assert Solution().smallestGoodBase("13") == "3"  # example 1
assert Solution().smallestGoodBase("4681") == "8"  # example 2
assert Solution().smallestGoodBase("1000000000000000000") == "999999999999999999"  # example 3

# Edge cases
assert Solution().smallestGoodBase("3") == "2"  # smallest possible n
assert Solution().smallestGoodBase("4") == "3"  # n = 4, base 3 gives 11
assert Solution().smallestGoodBase("7") == "2"  # n = 7, base