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.

Difficulty: interview

Starter code:

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        

Solutions:
import math
 class Solution:
     def smallestGoodBase(self, n):
         n = int(n)
         maxLength = int(math.log(n,2))
         for m in range(maxLength, 1, -1):
             k = int(n**m**-1)
             if (k**(m+1) - 1)//(k - 1) == n:
                 return str(k)
         return str(n-1)
         """
         :type n: str
         :rtype: str
         """
         

#
 # [483] Smallest Good Base
 #
 # https://leetcode.com/problems/smallest-good-base/description/
 #
 # algorithms
 # Hard (33.74%)
 # Total Accepted:    6.7K
 # Total Submissions: 20K
 # Testcase Example:  '"13"'
 #
 # 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.
 #
 #
 #
 from math import log
 class Solution:
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """
         num = int(n)
         bit = int(log(num, 2))
         for b in range(bit, 1, -1) :
             base = int(num ** b ** -1)
             # print(b, base)
             if (base ** (b + 1) - 1) // (base - 1) == num :
                 return str(base)
         return str(num - 1)


class Solution:
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """
         import math
         n=int(n)
         max_m=int(math.log2(n))
         
         for m in range(max_m,1,-1):
             
             k=int(n**(m**(-1)))
             if n==(k**(m+1)-1)//(k-1):
                return str(k)
         return str(n-1)

from math import log
 class Solution:
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """
         num = int(n)
         
         #use binary search the base
         for size in range(int(log(num+1,2)), 1, -1):
             #find the base
             l,r = 2, int(pow(num, 1.0 / (size - 1)) +1)
             while l<r:
                 mid = l+(r-l)//2
                 sum=0
                 for i in range(size):
                     sum=sum*mid+1
                 if sum==num:
                     return str(mid)
                 elif sum<num:
                     l=mid+1
                 else:
                     r=mid
         return str(num-1)
         
     #           long long num = stol(n);
     #     for (int i = log(num + 1) / log(2); i >= 2; --i) {
     #         long long left = 2, right = pow(num, 1.0 / (i - 1)) + 1;
     #         while (left < right) {
     #             long long mid = left + (right - left) / 2, sum = 0;
     #             for (int j = 0; j < i; ++j) {
     #                 sum = sum * mid + 1;
     #             }
     #             if (sum == num) return to_string(mid);
     #             else if (sum < num) left = mid + 1;
     #             else right = mid;
     #         }
     #     }
     #     return to_string(num - 1);
     # }
         

#
 # [483] Smallest Good Base
 #
 # https://leetcode.com/problems/smallest-good-base/description/
 #
 # algorithms
 # Hard (33.74%)
 # Total Accepted:    6.7K
 # Total Submissions: 20K
 # Testcase Example:  '"13"'
 #
 # 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.
 #
 #
 #
 from math import log
 class Solution:
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """
         num = int(n)
         bit = int(log(10, 2) * len(n) + 1)
         while bit > 0 :
             low, high = 2, int(num ** (1.0 / bit) + 1)
             while low <= high :
                 base = low + (high - low) // 2
                 tmp = 0
                 for _ in range(bit + 1) :
                     tmp = tmp * base + 1
                 # print(bit, low, high, base, tmp)
                 if tmp == num :
                     return str(base)
                 elif tmp < num :
                     low = base + 1
                 else :
                     high = base - 1
             bit -= 1
         return str(num - 1)


class Solution(object):
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """        
         num = int(n)
         thisLen = int(math.log(num,2)) + 1
         while thisLen > 2:
             # from equation [3], we havve
             thisBase = int(num ** (1.0/(thisLen - 1)))
             # from equation [2], we have
             if num * (thisBase - 1) == thisBase ** thisLen - 1:
                 return str(thisBase)
             thisLen -= 1
         return str(num - 1)

class Solution:
     def smallestGoodBase(self, n):
         """
         :type n: str
         :rtype: str
         """
         return self.use_binary_search(n)
         
     def use_math(self, n):
         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)  # Refer [6]
             if (k**(m+1)-1)//(k-1) == n:
                 # Refer [3]
                 return str(k)
         
         return str(n-1)  
     
     def use_binary_search(self, n):
         n = int(n)
         
         for d in range(60, 0, -1):
             if (1 << d) < n:
                 base = self.binary_search(n, d)
                 if base:
                     return str(base)
         
         return str(n-1)
     
     def binary_search(self, n, d):
         lo, hi = 1, int(pow(n, 1.0/d) + 1)
         
         while lo < hi:
             mid = lo + (hi - lo) // 2
             total = 1
             for i in range(1, d+1):
                 total += mid ** i
             
             if total == n:
                 return mid
             elif total < n:
                 lo = mid + 1
             else:
                 hi = mid
         
         return 0