[LintCode] Pow(x, n)

java 6 2016-02-29 13:03
女装

Problem

Implement pow(x, n).

Example

Pow(2.1, 3) = 9.261
Pow(0, 1) = 0
Pow(1, 0) = 1

Note

You don't need to care about the precision of your answer, it's acceptable if the expected answer and your answer 's difference is smaller than 1e-3.

Challenge

O(logn) time

Solution

When you see O(logn) time for a obvious O(n) time question, think about binary search and recursion.

public class Solution {
    public double myPow(double x, int n) {
        boolean isNeg = false;
        if (n == 0) return 1;
        if (n == 1) return x;
        if (n < 0) {
            isNeg = true;
            n = -n;
        }
        int k = n / 2;
        int l = n - 2 * k;
        double rk = myPow(x, k);
        double rl = myPow(x, l);
        double res = rk * rk * rl;
        if (isNeg) return 1 / res;
        else return res;
    }
}
女装
文章评论