Welcome to Subscribe On Youtube

483. 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.

Solutions

  • 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;
        }
    }
    
    
  • class Solution {
    public:
        string smallestGoodBase(string n) {
            long v = stol(n);
            int mx = floor(log(v) / log(2));
            for (int m = mx; m > 1; --m) {
                int k = pow(v, 1.0 / m);
                long mul = 1, s = 1;
                for (int i = 0; i < m; ++i) {
                    mul *= k;
                    s += mul;
                }
                if (s == v) {
                    return to_string(k);
                }
            }
            return to_string(v - 1);
        }
    };
    
  • 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)
    
    

All Problems

All Solutions