leetcode/0050-powx-n.cpp at master · Jamesweng/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    double fun(double x, int n) {
        if (n == 0) {
            return 1.;
        }
        if (n == 1) {
            return x;
        }
        double b = fun(x, n / 2);
        b *= b;
        if (n % 2 == 1) b *= x;
        return b;
    }
    double myPow(double x, int n) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        if (n == 0) {
            return 1.0;
        }
        double y = x;
        if (x < 0) x = -x;
        int m;
        double z = 1.0;
        if (n < 0) {
            if (n == -2147483648) {
                m = 2147483647;
                z = x;
            } else {
                m = -n;
            }

        } else {
            m = n;
        }
        double b = fun(x, m);
        b *= z;
        if (n < 0) b = 1.0 / b;
        if (y < 0) {
            if (n % 2 == 1) b = -b;
        }
        return b;
    }
};
// pow(x, n) = pow(x, n / 2) * pow(x, n / 2);
// if n % 2 == 0, *= x