題目

對于給定的整數(shù) n, 如果n的k（k>=2）進制數(shù)的所有數(shù)位全為1，則稱 k（k>=2）是 n 的一個好進制。

以字符串的形式給出 n, 以字符串的形式返回 n 的最小好進制。

• 示例 1：

輸入：“13”
輸出：“3”
解釋：13 的 3 進制是 111。

• 示例 2：

輸入：“4681”
輸出：“8”
解釋：4681 的 8 進制是 11111。

• 示例 3：

輸入：“1000000000000000000”
輸出：“999999999999999999”
解釋：1000000000000000000 的 999999999999999999 進制是 11。

提示：

• n的取值范圍是 [3, 10^18]。
• 輸入總是有效且沒有前導(dǎo) 0。

等比數(shù)列求和

如果n的k（k>=2）進制數(shù)的所有數(shù)位全為1，那么可以表示為一個等比數(shù)列相加

因此根據(jù)等比數(shù)列求和公式可得

變形得：

因為n的取值范圍是 [3, 10^18]并且k>=2,根據(jù)log函數(shù)的單調(diào)性可得:m<60

二項式定理

根據(jù)二項式定理可得

又因為

二式結(jié)合可得

最終可求得k

解題思路

根據(jù)等比數(shù)列求和，我們可以快速得到m的最大值，從而縮小我們的搜索范圍

2. 根據(jù)上一步得出的m的取值范圍進行遍歷，通過二項式定理得出的結(jié)論

可以求出k值，再檢驗當(dāng)前k值能否組成n

代碼

class Solution {public String smallestGoodBase(String n) {long num = Long.parseLong(n);int maxL = (int) Math.floor(Math.log(num) / Math.log(2));for (int m=maxL;m>1;m--){int k = (int) Math.pow(num, 1.0 / m);long cur=1,pow=1;for(int i=0;i<m;i++){pow*=k;cur+=pow;}if(cur==num)return String.valueOf(k);}return String.valueOf(num-1);} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 483. 最小好进制的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。