Algorithm
Problem Name: 483. Smallest Good Base
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:
nis an integer in the range[3, 1018].ndoes not contain any leading zeros.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const smallestGoodBase = function(n) {
const N = BigInt(n),
bigint2 = BigInt(2),
bigint1 = BigInt(1),
bigint0 = BigInt(0)
let maxLen = countLength(N, bigint2)
for (let length = maxLen; length > 0; length--) {
let [found, base] = findMatchInHalf(length)
if (found) return '' + base
}
return '' + (N - 1)
function findMatchInHalf(length, smaller = bigint2, bigger = N) {
if (smaller > bigger) return [false]
if (smaller === bigger) {
return [valueOf1s(smaller, length) === N, smaller]
}
let mid = (smaller + bigger) / bigint2
let val = valueOf1s(mid, length)
if (val === N) return [true, mid]
if (val > N) return findMatchInHalf(length, smaller, mid - bigint1)
return findMatchInHalf(length, mid + bigint1, bigger)
}
function valueOf1s(base, lengthOf1s) {
let t = bigint1
for (let i = 1; i < lengthOf1s; i++) {
t *= base
t += bigint1
}
return t
}
function countLength(N, base) {
let t = N,
len = 0
while (t > bigint0) {
t /= base
len++
}
return len
}
}
Input
n = "13"
Output
"3"
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def smallestGoodBase(self, n):
n = int(n)
for m in range(int(math.log(n, 2)), 1, -1):
k = int(n ** m ** -1)
if (k ** (m + 1) -1) // (k - 1) == n:
return str(k)
return str(n-1)
Input
n = "13"
Output
"3"