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.

Description Solution Video 14:28

483. Smallest Good Base

Hard47.6% acceptance3 companies

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, 10¹⁸].
n does not contain any leading zeros.

Asked at 3 companies

Google Amazon Microsoft

Topics

Binary Search Math

14:28

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def smallestGoodBase(self, n: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"13"

Input

"4681"

Input

"1000000000000000000"

Your code is saved on this device.Solution