runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: recursion, math

Pow(x, n)

๐Ÿ“– description

็ตฆๅฎšๆ•ธๅญ— x ่ˆ‡ๆฌกๆ•ธ n ๏ผŒๆฑ‚ x^n ใ€‚

ex.
    Input: 
        x = 2.00000, n = 10

    Output: 
        1024.00000

๐Ÿง  solution

ๅฟซ้€Ÿๅ†ช + ่จ˜ๆ†ถ็ตๆžœ๏ผŒๅฏไปฅๆŠŠๆ™‚้–“่ค‡้›œๅบฆๅฃ“ๅˆฐ O(log(n)) ๏ผŒๆธ›ๅฐ‘่จˆ็ฎ—้‡่ค‡็š„็‹€ๆ…‹ใ€‚

โณ time complexity

ๅฟซ้€Ÿๅ†ชๆ™‚้–“่ค‡้›œๅบฆ O(log(n))
็ธฝๆ™‚้–“่ค‡้›œๅบฆ O(log(n))

๐Ÿ“ code

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
class Solution {
public:
    unordered_map<long int,double> map;
    double power(double x,long int n){
        if(map.find(n)!=map.end()){     // ๅฆ‚ๆžœๆœ‰่จˆ็ฎ—้Ž
            return map[n];
        }
        else if(n==0){
            return 1;
        }
        
        double tmp = power(x,n/2);
        if(n%2==0){
            return map[n] = tmp * tmp;  // ่จ˜ๆ†ถ็ตๆžœ
        }
        else{
            return map[n] = tmp * tmp * x;
        }
    }
    double myPow(double x, int n) {
        if(x==1) return 1;
        long int m = n;
        if(n<0){
            return (double)1/power(x,-m);
        }
        else{
            return power(x,m);
        }
    }
};