Smallest Good Base - Video Solutions

Problem Overview: Given a number n (as a string), find the smallest base k ≥ 2 such that n written in base k consists only of 1s. In other words, n = 1 + k + k^2 + ... + k^m for some m ≥ 1. The challenge is that n can be very large, so brute forcing bases is not practical.

Approach 1: Binary Search for Base Length (O((log n)^2) time, O(1) space)

The representation 111...1 in base k forms a geometric series: n = (k^(m+1) - 1) / (k - 1). Instead of guessing the base directly, iterate over the possible length m + 1 of the representation. The maximum length occurs when k = 2, which gives about log2(n) digits. For each candidate length, run a binary search on the base k. During the search, compute the geometric sum incrementally to avoid overflow. If the sum equals n, that base is valid. Because the outer loop runs about log n times and each binary search also takes log n, the total complexity is roughly O((log n)^2). This approach is reliable and handles very large values cleanly.

Approach 2: Iterative Check on Powers (O((log n)^2) time, O(1) space)

Another way is to iterate over possible lengths of the representation and directly estimate the base using powers. For a sequence of m + 1 ones, the base is approximately k ≈ n^(1/m). Compute this candidate base using floating point, then verify it by reconstructing the sum 1 + k + k^2 + ... + k^m. The verification step uses integer multiplication to avoid precision issues. If the computed sum equals n, that base is valid. This method avoids explicit binary search but still relies on checking up to log n possible lengths and performing O(m) multiplication steps for validation.

Both approaches rely heavily on properties of geometric progressions and large integer arithmetic, which makes the problem primarily a math and binary search exercise rather than a typical data structure problem. Care must be taken to stop multiplication early if the partial sum exceeds n, preventing overflow and unnecessary work.

Recommended for interviews: The binary search on base length is the approach most interviewers expect. It demonstrates that you recognize the geometric series pattern and know how to combine mathematical insight with binary search. Explaining the maximum length bound (log2(n)) shows deeper reasoning. The iterative power-check method is also valid, but binary search communicates stronger algorithmic thinking.