Concise C++ Binary Search solution


  • 2
    H

    The idea is similar to the other solutions

    class Solution {
    public:
        string smallestGoodBase(string n) {
            typedef unsigned long long ll;
            ll num = stol(n);
            for (ll p = log(num+1) / log(2); p >= 2; --p) {
                ll lk = 2, rk = pow(num, 1.0 / (p-1))+1;
                while (lk <= rk) {
                    ll mk = lk + (rk - lk) / 2, sum = 0;
                    for (ll i = 0, f = 1; i < p; ++i, f *= mk)
                        sum += f;
                    if (sum < num) lk = mk+1;
                    else if (sum > num) rk = mk-1;
                    else return to_string(mk);
                }
            }
            return to_string(num-1);
        }
    };

  • 0

    Concise Code. Let me add some comments to helper others understand your code.

    class Solution {
    public:
        string smallestGoodBase(string n) {
            using ull = unsigned long long;
            // num - 1 is the largest possible base
            ull num = stoll(n);
            // this loop will iterate length from max possible value to min value
            // when base == 2, we have longest length of '1'
            // 2^0 + 2^1 + ... + 2^(len - 1) == num -> 2^len == num + 1 -> len = log(num + 1) base on 2
            // log(num + 1) / log(2) == log (num + 1) base on 2
            for (int len = log(num + 1) / log(2); len >= 2; len--) {
                // use binary search to find possible base
                // b^0 + b^1 + .... + b^(len - 1) == num ->
                // b^(len - 1) <= num + 1 ->
                // b <= pow(num + 1, 1.0 / (len - 1)) 
                ull l = 2, r = pow(num + 1, 1.0 / (len - 1)) + 1;
                while (l < r) {
                    ull sum = 0, base = l + (r - l) / 2, val = 1;
                    for (int i = 0; i < len; i++, val *= base)
                        sum += val;
                    if (sum == num)
                        return to_string(base);
                    else if (sum < num)
                        l = base + 1;
                    else
                        r = base;
                }
            }
            return to_string(num - 1);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.