smallest-good-base

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given an integer <code>n</code> represented as a string, return the smallest good base of <code>n</code>.

We call <code>k &gt;= 2</code> a good base of <code>n</code>, if all digits of <code>n</code> base <code>k</code> are <code>1</code>&#39;s.

&nbsp;
Example 1:

<pre>
Input: n = &quot;13&quot;
Output: &quot;3&quot;
Explanation: 13 base 3 is 111.
</pre>

Example 2:

<pre>
Input: n = &quot;4681&quot;
Output: &quot;8&quot;
Explanation: 4681 base 8 is 11111.
</pre>

Example 3:

<pre>
Input: n = &quot;1000000000000000000&quot;
Output: &quot;999999999999999999&quot;
Explanation: 1000000000000000000 base 999999999999999999 is 11.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n</code> is an integer in the range <code>[3, 1018]</code>.</li>
	<li><code>n</code> does not contain any leading zeros.</li>
</ul>

smallestGoodBase

Smallest Good Base

Math

Binary Search

以字符串的形式给出 <code>n</code>&nbsp;, 以字符串的形式返回 <code>n</code> 的最小 好进制 &nbsp;。

如果 <code>n</code> 的 &nbsp;<code>k(k&gt;=2)</code>&nbsp;进制数的所有数位全为1，则称&nbsp;<code>k(k&gt;=2)</code>&nbsp;是 <code>n</code> 的一个&nbsp;好进制&nbsp;。

&nbsp;

示例 1：

<pre>
输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。
</pre>

示例 2：

<pre>
输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。
</pre>

示例 3：

<pre>
输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n</code> 的取值范围是&nbsp;<code>[3, 1018]</code></li>
	<li><code>n</code> 没有前导 0</li>
</ul>