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:

The range of n is [3, 10^18].
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);
    }
};

Java

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);
    }
}

// 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)

483 - Smallest Good Base

483. Smallest Good Base (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions

Welcome to Subscribe On Youtube

483. Smallest Good Base (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions