Power, Binary Exponentiation and Matrix Exponentiation

Binary Exponentiation

Watch this video

After watching above video, the problem below will be a piece of cake.

50. Pow(x, n)

class Solution {
public:
    double helper(double x, long n)
    {
        if(n==0)return 1.0;
        if(n<0)return 1/helper(x, -n);
        else
        {
            auto ret = helper(x, n/2);
            ret *= ret;
            if(n%2)ret *= x;
            return ret;
        }
        return 0.0;
    }
    double myPow(double x, int n) 
    {
        return helper(x, long(n)); 
    }
};

Matrix Exponentiation

Watch this video.

Reference

[1] https://oi-wiki.org/math/quick-pow/