483. Smallest Good Base

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

We call k >= 2 a good base of n, if all digits of n base k are 1’s.

c++

class Solution {
    unsigned long long helper(long long n, long long d) {
        unsigned long long l = 1, r = pow(n, 1.0 / d) + 1;
        while(l <= r) {
            unsigned long long mid = l + (r - l) / 2;
            unsigned long long sum = 0;
            for(unsigned long long i = 0, mul = 1; i <= d; i++, mul *= mid) {
                sum += mul;
            }
            if(sum == n) return mid;
            if(sum > n) r = mid - 1;
            else l = mid + 1;
        }
        return 0;
    }
public:
    string smallestGoodBase(string n) {
        unsigned long long num = stoll(n);
        for(int i = log2(num); i >= 1; i--) {
            unsigned long long res = helper(num, i);
            if(res) return to_string(res);
        }
        return to_string(num - 1);
    }
};