iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 25
1
Software Development

LeetCode30系列 第 25

[LeetCode30] Day25 - 483. Smallest Good Base

題目

如果進制為kn的所有位數均為1,則稱knGood base

給定一個以string儲存的整數n,求 Smallest Good Base。

  • Notes
    • k>=2
    • n範圍: [3, 10^18]
    • 儲存n的string不具前導0
      • e.g. n=1234567,不會出現 0001234567。

解析

  • 不管如何,先將string轉回數字,才好使用。
    • 因為範圍只到10^18,使用unsigned long long 就能儲存了。
    uint64_t ull_n = stoull(n);
    
  • 接著考慮一下k的範圍,這樣才不用多算沒用的東西。
    • 題目說k>=2
    • 那以k=2至少需要幾位元才能表達n?
      • 2^b >= n
      • 反過來說, 2 = ceil( n^(1/b) ),如果用比b大的值,算出來的base就會小於2。
      • 則能得max如下,記得這max是至少需要的位元數,不是base,但能透過來算出base.
      • min則會是2,這不用多說了吧
      uint64_t min = 2
      uint64_t max = log2(ull_n) + 1 
      
  • 有了[min,max],我們能用for loop,算出每個可能的k,並去看是否符合Good base規定。
    • 這裡i從max開始,即是從最小base開始,有找到就能結束了
    • 先算k,k<2的跳過。
    • 接著算sum為以k為基底的111...1,下面j=1~i+1,因為i是所需位元數,如果在這之間都是每位都是1還不能等於n,那就不會是了。
 for(uint64_t i = max; i >= min; i--){
    uint64_t k = pow(ull_n, 1.0/i); //
    if(k < 2){
        continue;
    }

    uint64_t sum = 0; 
    uint64_t prod = 1;

    for(uint64_t j = 1; j <= i + 1; j++){
        sum += prod;
        prod *= k;
    }

    if(sum == ull_n){
        return to_string(k);
    }
}

完整Code

class Solution {
public:
    string smallestGoodBase(string n) {
        
        uint64_t ull_n = stoull(n);
        uint64_t min = 2;
        uint64_t max = log2(ull_n) + 1;
        
        for(uint64_t i = max; i >= min; i--){
            uint64_t k = pow(ull_n, 1.0/i); //
            if(k < 2){
                continue;
            }
            
            uint64_t sum = 0; 
            uint64_t prod = 1;
            
            for(uint64_t j = 1; j <= i + 1; j++){
                sum += prod;
                prod *= k;
            }
            
            if(sum == ull_n){
                return to_string(k);
            }
        }
        
        return to_string(ull_n - 1);
    }
};

https://ithelp.ithome.com.tw/upload/images/20201007/201291478i1AWzD9qH.png


上一篇
[LeetCode30] Day24 - 458. Poor Pigs
下一篇
[LeetCode30] Day26 - 1106. Parsing A Boolean Expression
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言