Smallest Good Base solution and explanation
Google
7 more videos on this problem
483. Smallest Good Base | leetcode | Binary Search ApproachAshwani Kansal · 14:28 · 2K views
Leetcode 0483. Smallest Good BaseFearless Learner · 24:43 · 1K views
【每日一题】483. Smallest Good Base, 10/23/2019Huifeng Guan · 57:16 · 1K views
Code Review: LeetCode 483: Smallest Good BaseRoel Van de Paar · 2:59 · 424 views
LeetCode 483: Smallest Good BaseAlitaCode · 27:43 · 150 views
117. LeetCode 483. Smallest Good Base [ Javascript ]Web Fusion with Bharadwaj · 5:58 · 132 views
No Sound Leetcode 483: Smallest Good BaseExtremeProgrammer · 1:06 · 87 views
Chatgpt C++ leetcode 483. Smallest Good BaseWindows 8.1 Tails Prower Ultra · 3:30 · 4 views
The 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.
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:
nis an integer in the range[3, 1018].ndoes not contain any leading zeros.
Approach overview
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.
Approach 1: Binary Search for Base Length
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.
def smallest_good_base(n: str) -> str:
n = int(n)
max_m = n.bit_length() # maximum possible m
for m in range(max_m, 1, -1):
k = int(pow(n, 1.0 / (m - 1)))
if (pow(k, m) - 1) // (k - 1) == n:
return str(k)
return str(n - 1)#include <cmath>
#include <string>
using namespace std;
string smallestGoodBase(string n) {
long long num = stol(n);
int max_m = log2(num) + 1;
for (int m = max_m; m >= 2; --m) {
long long k = pow(num, 1.0 / (m - 1));
long long sum = 1, current_pow = 1;
for (int i = 1; i < m; ++i) {
current_pow *= k;
sum += current_pow;
}
if (sum == num) return to_string(k);
}
return to_string(num - 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.
Approach 2: Iterative Check on Powers
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.
public class Solution {
public String smallestGoodBase(String n) {
long num = Long.parseLong(n);
for (int m = 62; m >= 2; m--) {
long left = 2, right = num - 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long sum = 0, base = 1;
for (int i = 0; i < m; i++) {
sum = sum * mid + 1;
}
if (sum == num) return Long.toString(mid);
else if (sum < num) left = mid + 1;
else right = mid - 1;
}
}
return Long.toString(num - 1);
}
}function smallestGoodBase(n) {
let num = BigInt(n);
for (let m = num.toString(2).length; m >= 2; m--) {
let left = 2n, right = num - 1n;
while (left <= right) {
let mid = (left + right) / 2n;
let sum = 1n, base = 1n;
for (let i = 1; i < m; i++) {
base *= mid;
sum += base;
}
if (sum === num) return mid.toString();
if (sum < num) left = mid + 1n;
else right = mid - 1n;
}
}
return (num - 1n).toString();
}This Java solution uses embedding within a power loop to efficiently construct and check each attempted number long k against the target n.
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.
Complexity comparison
| 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. |
Complexity analysis
| 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 |
Frequently asked questions
Is Smallest Good Base easy or hard?
Smallest Good Base is classified as a Hard problem. The difficulty comes from recognizing the geometric series representation and efficiently searching the base space using logarithmic bounds rather than brute force.
Smallest Good Base Python/Java solution
Python, Java, C++, and JavaScript implementations typically iterate over possible digit lengths and check whether a base satisfies the geometric series sum. Python solutions often use integer arithmetic with loops, while Java and C++ versions must guard against overflow when multiplying powers.
How to solve Smallest Good Base in O(n)?
An O(n) approach is not practical because n can be extremely large (up to 10^18). Instead, efficient solutions rely on logarithmic bounds. By limiting the number of digits to log2(n) and checking bases using binary search or power validation, the problem is solved in about O((log n)^2) time.
What is the best approach for Smallest Good Base?
The most reliable approach is iterating over possible representation lengths and performing binary search on the base. The equation n = 1 + k + k^2 + ... + k^m forms a geometric series, so binary search helps find the base efficiently. This method runs in about O((log n)^2) time and constant space while safely handling very large numbers.
Is Smallest Good Base asked at Google/Amazon/Meta?
Smallest Good Base is a classic math-heavy interview problem that appears in advanced algorithm rounds at companies like Google and occasionally Amazon. It tests mathematical reasoning, geometric series manipulation, and careful handling of large integers rather than standard data structures.
What data structure is used in Smallest Good Base?
The problem does not rely on complex data structures. It mainly uses mathematical formulas, exponentiation, and binary search. The focus is on evaluating geometric series and preventing overflow while checking candidate bases.
What is the time complexity of Smallest Good Base?
The optimal solutions run in approximately O((log n)^2) time with O(1) space. There are up to log2(n) possible lengths of the representation, and for each length the algorithm either performs a binary search on the base or validates the geometric sum using iterative multiplication.