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.
Examples
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.
Solution
Method 1 – Binary Search for Base Length
Intuition
A number n can be written as 1 + k + k^2 + … + k^m for some base k and integer m ≥ 1. For each possible m (from max to 1), we can binary search for k such that this sum equals n. The smallest k > 1 found is the answer.
Approach
- For m from max possible (log2(n)) down to 1:
- Use binary search to find k in [2, n^(1/m)+1] such that 1 + k + … + k^m == n.
- If found, return k as string.
- If no such k found, return n-1 (since n = 1 + (n-1)).
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O((log n)^2)
, since for each m (up to log n), we binary search for k (up to log n steps), and each check is O(log n). - 🧺 Space complexity:
O(1)
, only constant extra space is used.
Method 2 - Mathematical Formula
Intuition
For each possible length m, we can try to solve the equation n = (k^{m+1} - 1) / (k - 1) for integer k > 1. If k is integer and the sum matches n, return k.
Approach
- For m from max possible (log2(n)) down to 1:
- Compute k = int(n ** (1/m)).
- If (k^m+1 - 1) // (k - 1) == n, return k.
- If no such k found, return n-1.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O((log n)^2)
, for each m (up to log n), we try a candidate k and check the sum in O(log n). - 🧺 Space complexity:
O(1)
, only constant extra space is used.