C++ 3m Solution - Solve Equation By Binary Search


  • 0
    F
    class Solution {
        long long f(long long b, int n)
        {
            long long k = 1;
            for (int i = 1; i < n; ++i)
                k = k*b + 1;
            return k;
        }
        long long solve(long long k, int n)
        {
            long long bl = pow(k, 1./n), bh =  pow(k, 1./(n - 1) );
            if (n == 2) bh = k;
            while(bl <= bh)
            {
                long long mid = bl + (bh - bl) /2;
                long long t = f(mid, n);
                if (t > k)
                    bh = mid - 1;
                else if (t < k)
                    bl = mid + 1;
                else
                    return mid;
            }
            return -1;
        }
    public:
        string smallestGoodBase(string s) {
            long long k = stoll(s);
            for (int i = log2(k) + 1; i >= 3; --i )
            {
                long long b = solve(k, i);
                if (b != -1)
                    return to_string(b);
            }
            return to_string(k - 1);
            
        }
    };
    
    

Log in to reply
 

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