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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics

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

Solutions:
class Solution:

	def smallestGoodBase(self, n):
		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)


class Solution(object):

	def smallestGoodBase(self, n):
		num = int(n)
		thisLen = int(math.log(num, 2)) + 1
		while thisLen > 2:
			thisBase = int(num ** (1.0 / (thisLen - 1)))
			if num * (thisBase - 1) == thisBase ** thisLen - 1:
				return str(thisBase)
			thisLen -= 1
		return str(num - 1)


class Solution:

	def smallestGoodBase(self, n):
		return self.use_binary_search(n)

	def use_math(self, n):
		n = int(n)
		max_m = int(math.log(n, 2))
		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)

	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