Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/483.html

483. Smallest Good Base (Hard)

For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.

Now given a string representing n, you should return the smallest good base of n in string format.

Example 1:

Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.

 

Example 2:

Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

 

Example 3:

Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

 

Note:

  1. The range of n is [3, 10^18].
  2. The string representing n is always valid and will not have leading zeros.

 

Related Topics:
Math, Binary Search

Solution 1.

n - 1 is the greatest good base since n base(n-1) = 11.

Assume x is the next smaller good base, then n base(x) = 111 or x^2 + x + 1 = n. x = sqrt(n - x - 1) < sqrt(n).

Let k = sqrt(n) and assume val base(k) = 111. val should be greater than n.

Then we keep decrement k to approach x, and the val which satisfies val base(k) = 111 approaches n as well.

We keep decrementing k until val <= num.

If val == n, we find a good base k; otherwise (val < n), k is not a good base.

We continue to look for the next smaller good base y, then n base(y) = 1111 or y^3 + y^2 + y + 1 = n. y = cbrt(n - y^2 - y - 1) < cbrt(n).

So we can do similar approach as above, let k = cbrt(n) and try to approach y.

As we keep looking for the next good base z, we start from k = pow(n, 1 / (cnt - 1)) where cnt is the number of ones in n base(z).

We stop the process once k < 2. The last good base we found is the answer.

// OJ: https://leetcode.com/problems/smallest-good-base/
// Time: O(logN)
// Space: O(1)
typedef unsigned long long ULL;
class Solution {
private:
    ULL getValue(ULL base, int cnt) {
        ULL ans = 1, p = 1;
        while (--cnt) ans += (p *= base);
        return ans;
    }
public:
    string smallestGoodBase(string n) {
        ULL num = stoull(n), ans = num - 1, cnt = 3, k, val;
        while (true) {
            k = pow(num, 1 / (double)(cnt - 1));
            if (k < 2) break;
            do {
                val = getValue(k, cnt);
                if (val == num) ans = k;
                --k;
            } while (val > num);
            ++cnt;
        }      
        return to_string(ans);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/smallest-good-base/
// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/smallest-good-base/discuss/96590/3ms-AC-C++-long-long-int-+-binary-search/101166
class Solution {
    typedef unsigned long long ull;
public:
    string smallestGoodBase(string n) {
        ull num = (ull)stoll(n);
        int maxlen = log(num) / log(2) + 1;
        for(int k = maxlen; k >= 3; --k){
            ull b = pow(num, 1.0 / (k - 1)), sum = 1, cur = 1;
            for (int i = 1; i < k; ++i) sum += (cur *= b);
            if (sum == num) return to_string(b);
        }  
        return to_string(num - 1);
    }
};
  • class Solution {
        public String smallestGoodBase(String n) {
            long num = Long.parseLong(n);
            long max = (long) (Math.log(num) / Math.log(2));
            for (long i = max; i > 1; i--) {
                long base = (long) Math.pow(num, 1.0 / i);
                long sum = 0;
                for (long j = 0; j <= i; j++)
                    sum = sum * base + 1;
                if (sum == num)
                    return String.valueOf(base);
            }
            return String.valueOf(num - 1);
        }
    }
    
    ############
    
    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;
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/smallest-good-base/
    // Time: O(logN)
    // Space: O(1)
    typedef unsigned long long ULL;
    class Solution {
    private:
        ULL getValue(ULL base, int cnt) {
            ULL ans = 1, p = 1;
            while (--cnt) ans += (p *= base);
            return ans;
        }
    public:
        string smallestGoodBase(string n) {
            ULL num = stoull(n), ans = num - 1, cnt = 3, k, val;
            while (true) {
                k = pow(num, 1 / (double)(cnt - 1));
                if (k < 2) break;
                do {
                    val = getValue(k, cnt);
                    if (val == num) ans = k;
                    --k;
                } while (val > num);
                ++cnt;
            }      
            return to_string(ans);
        }
    };
    
  • 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)
    
    ############
    
    import math
    
    
    class Solution(object):
      def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        n = int(n)
        max_m = int(math.log(n, 2))  # Refer [7]
        for m in range(max_m, 1, -1):
          k = int(n ** m ** -1)
          if (k ** (m + 1) - 1) / (k - 1) == n:
            return str(k)
        return str(n - 1)
    
    

All Problems

All Solutions