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.
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.
Constraints:
n is an integer in the range [3, 1018].n does not contain any leading zeros.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.
We aim to find the smallest base k for which the number n can be represented as all 1's. This implies that n can be written as 1 + k + k^2 + k^3 + ... + k^(m-1) for some integer m. We can perform a binary search over possible values of m, since the maximum number of terms for which the number is strictly increasing is log2(n) + 1.
This Python solution leverages the binary search technique by iterating over possible lengths of all '1's representation (from highest to lowest). For each possible m, it computes the possible base k by taking the m-1 root of n and checks if the series sum equals n.
Time Complexity: O(log(n) * log(n)) due to iterating over possible values of m and calculating powers.
Space Complexity: O(1) because only a constant amount of space is used.
We can directly iterate and check powers of each candidate base from 2 up to the number n-1. In each iteration, try building the number n by forming a geometric series with base k.
This Java solution uses embedding within a power loop to efficiently construct and check each attempted number long k against the target n.
Java
JavaScript
Time Complexity: O(n log n), dependent on iterating over possible base values and depth of power calculation.
Space Complexity: O(1), given only scalars are maintained.
| Approach | Complexity |
|---|---|
| Binary Search for Base Length | Time Complexity: O(log(n) * log(n)) due to iterating over possible values of m and calculating powers. |
| Iterative Check on Powers | Time Complexity: O(n log n), dependent on iterating over possible base values and depth of power calculation. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search for Base Length | O((log n)^2) | O(1) | Best general solution for very large n; stable and precise using integer checks |
| Iterative Check on Powers | O((log n)^2) | O(1) | When estimating the base via n^(1/m) is simpler to implement and precision checks are manageable |
483. Smallest Good Base | leetcode | Binary Search Approach • Ashwani Kansal • 2,581 views views
Watch 6 more video solutions →Practice Smallest Good Base with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor