483. Smallest Good Base

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:

1. The range of n is [3, 10^18].
2. The string representing n is always valid and will not have leading zeros.

# @lc code=start
using LeetCode

function smallest_good_base(n::Int)
    for m in 62:-1:2
        k = floor(Int, n^(1 / m))
        k ≤ 1 && continue
        s = (Int128(k)^(m + 1) - 1) ÷ (k - 1)
        (s == n) && return k
    end
    n - 1
end
# @lc code=end

smallest_good_base (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.