, 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

Java

class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        for (int m = (int)(Math.log(num) /

Related Tags