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: Math

• Time complexity: O(log²n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} n
 * @return {string}
 */
const smallestGoodBase = function (n) {
  const num = BigInt(n);
  const maxLogarithm = Math.floor(Math.log2(n));

  for (let logarithm = maxLogarithm; logarithm >= 2; logarithm--) {
    const base = BigInt(Math.floor(Math.pow(n, 1 / logarithm)));
    let current = (sum = BigInt(1));

    for (let index = 0; index < logarithm; index++) {
      current *= base;
      sum += current;
    }
    if (sum === num) return `${base}`;
  }
  return `${num - 1n}`;
};