LeetCode 50 Pow(x,n)

LeetCode50 Pow(x,n)

Title Description

Realization pow(x, n) , Computation x Of n Power function

Examples

 Input : 2.00000, 10
 Output : 1024.00000

 Input : 2.10000, 3
 Output : 9.26100

 Input : 2.00000, -2
 Output : 0.25000
 explain : 2-2 = 1/22 = 1/4 = 0.25

Algorithm analysis

• Fast power
  

Time complexity

\(O(logn)\)

Java Code

class Solution {

    static double qmi(double a, long k){
        double res = 1;
        while( k > 0 ){
            if((k & 1) == 1) res *= a;
            k >>= 1;
            a *= a;

        }

        return res;
    }

    public double myPow(double x, int n) {
        long num = n;
        double t = qmi(x,Math.abs(num));
        if(n < 0) return 1/t;
        return t;
    }
}