Question

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

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

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