50 Pow(x, n)

50. Pow(x, n)

1. Question

Implement pow(x,n).

Example 1:

Input: 2.00000, 10

Output: 1024.00000

Example 2:

Input: 2.10000, 3

Output: 9.26100

2. Implementation

(1) 倍增法

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0.0;
        }

        double res = 1.0;

        while (n != 0) {
            if ((n & 1) == 1) {
                if (n > 0) {
                    res *= x;
                }
                else {
                    res /= x;
                }
            }
            x *= x;
            n /= 2;
        }
        return res;
    }
}

3. Time & Space Complexity

倍增法: 时间复杂度O(logn), 空间复杂度O(1)