Skip to content

483. Smallest Good Base

DifficultyHard

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.

Solutions

Thinking

The smallest base \(k\ge 2\) in which \(n\) is all ones. \(k=n-1\) always works (\(11_k\)), but \(n\) can be \(10^{18}\), so scanning \(k\) is impossible.

The number of ones \(m+1\) satisfies \(m<60\). Try \(m\) from large to small and binary-search \(k\) so that \(1+k+\cdots+k^m=n\). A larger \(m\) yields a smaller \(k\), so going downward finds the smallest base first.

The geometric sum is monotone in \(k\), so the binary search is valid. If none hits, fall back to \(n-1\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def smallestGoodBase(self, n: str) -> str:
        def cal(k, m):
            p = s = 1
            for i in range(m):
                p *= k
                s += p
            return s

        num = int(n)
        for m in range(63, 1, -1):
            l, r = 2, num - 1
            while l < r:
                mid = (l + r) >> 1
                if cal(mid, m) >= num:
                    r = mid
                else:
                    l = mid + 1
            if cal(l, m) == num:
                return str(l)
        return str(num - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        for (int len = 63; len >= 2; --len) {
            long radix = getRadix(len, num);
            if (radix != -1) {
                return String.valueOf(radix);
            }
        }
        return String.valueOf(num - 1);
    }

    private long getRadix(int len, long num) {
        long l = 2, r = num - 1;
        while (l < r) {
            long mid = l + r >>> 1;
            if (calc(mid, len) >= num)
                r = mid;
            else
                l = mid + 1;
        }
        return calc(r, len) == num ? r : -1;
    }

    private long calc(long radix, int len) {
        long p = 1;
        long sum = 0;
        for (int i = 0; i < len; ++i) {
            if (Long.MAX_VALUE - sum < p) {
                return Long.MAX_VALUE;
            }
            sum += p;
            if (Long.MAX_VALUE / p < radix) {
                p = Long.MAX_VALUE;
            } else {
                p *= radix;
            }
        }
        return sum;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string smallestGoodBase(string n) {
        long long num = stoll(n);
        for (int len = 63; len >= 2; --len) {
            long long radix = getRadix(len, num);
            if (radix != -1) {
                return to_string(radix);
            }
        }
        return to_string(num - 1);
    }

    long long getRadix(int len, long long num) {
        long long l = 2, r = num - 1;
        while (l < r) {
            long long mid = (l + r) >> 1;
            if (calc(mid, len) >= num) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return calc(r, len) == num ? r : -1;
    }

    long long calc(long long radix, int len) {
        long long p = 1, sum = 0;
        for (int i = 0; i < len; ++i) {
            if (LLONG_MAX - sum < p) {
                return LLONG_MAX;
            }
            sum += p;
            if (LLONG_MAX / p < radix) {
                p = LLONG_MAX;
            } else {
                p *= radix;
            }
        }
        return sum;
    }
};

Comments