C++ 3ms solution with explanation (no math derivation)


  • 0
    H

    It is obviously the base b must meets n = b^k + b^(k-1) + ... + b^1 + 1
    The straightforward way is to try from 2 to n, once it meets the formula above, we are done. But it will get TLE. To minimize the number of candidates, we do it from both directions: bottom-up and top-down.

    • For bottom-up: we set a LIMIT for k, as long as b^k + b^(k-1) + ... + b^1 + 1 > n, any larger number will not be able to form n with at least k+1 parts, in other word with b^k included. So, we are done.

    • For top-down: According to bottom-up result, just try from LIMIT-1 to 2.

    If both ways not able to find a valid base, then the answer is n-1 because (n-1)^1 + 1 = n.

    The value of LIMIT is used to balance the number of repeats between top-down and bottom-up loops

    #define LIMIT 8
    class Solution {
    public:
        string smallestGoodBase(string n) {
            long num = stol(n);
            for (int base = 2; sum(base, LIMIT) <= num; base++) {
                if (valid(num, base)) {
                    return to_string(base);
                }
            }
            
            for (int j = LIMIT-1; j > 1; j--) {
                long base = pow(num, 1.0/j);
                if (base < 2) continue;
                if (sum(base, j) == num) {
                    return to_string(base);
                }
            }
            return to_string(num-1);
        }
        
        bool valid(long n, int base) {
            while(n) {
                if (n % base != 1) return false;
                n /= base;
            }
            return true;
        }
        
        long sum(int base, int k) {
            long res = 1;
            long num = 1;
            for (int i = 0; i < k; i++) {
                num *= base;
                res += num;
            }
            return res;
        }
    };
    

Log in to reply
 

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