LogN solution C++


  • -1
    X
    //implement power(x, n)
    //corner case: if n == INT_MIN, cannot convert using INT_MAX
    class Solution {
    public:
        double myPow(double x, int n) {
            if (n == 0) return 1;
            int sign = n > 0 ? 1 : -1;
            bool intMinFlag = false;
            if (n == INT_MIN) {
                n = INT_MAX; //multiply one more time in the end
                intMinFlag = true;
            } else {
                n = abs(n); //using abs should always consider INT_MIN as a special case
            }
            double multiplier = x;
            power(x, multiplier, n);
            if (intMinFlag)
                x *= multiplier;
            if (sign == 1)
                return x;
            else
                return 1.0 / x;
        }
        
        void power(double& x, double multiplier, int n) {
            if (n == 1) {
                x = multiplier; return;
            }
            power(x, multiplier, n / 2);
            x = x * x;
            if (n % 2 == 1)
                x *= multiplier;
        }
    };

Log in to reply
 

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