0483. Smallest Good Base

https://leetcode.com/problems/smallest-good-base

Description

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.

ac

class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        int maxLen = (int) (Math.log(num + 1) / Math.log(2));
        for (int len = maxLen; len >= 0; len--) {
            long l = 2, r = (long) Math.pow(num, 1.0 / (len-1)) + 1;
            while (l < r) {
                long mid = l + (r-l)/2;
                long sum = 0;
                for (int i = 0; i < len; i++) sum = sum * mid + 1;

                if (sum == num) return ""+mid;
                else if (sum < num) l = mid + 1;
                else r = mid;
            }
        }

        return String.valueOf(num - 1);
    }
}

/*
1) every bit is 1, the length range is [2, log(n+1)/log2], for each length do binary search, from max to min, because max lenght leads to smaller base; 2) base range: [2, pow(n, 1.0/(len-1)) + 1], don't understand why it's the upper, binary search to find the base; 2) every bit is 1, so with candidate base and bits, calculate if it equals n;
*/