LeetCode

2013.12.17 13:56

Implement pow(x, n).

Solution:

　　Problem description is simple, so is the solution: divide and conquer. To calculae x^n, you'll need to know x^(n / 2) first.

　　Later, let's deal with boundary values:

　　　　1. n = 0

　　　　2. n > 0

　　　　3. n < 0

　　　　4. x < 0

　　　　5. x = 0.0 (IEEE754 zero)

　　　　6. x > 0

　　Think of any possible combinations and use your code for complete path coverage.

　　Time complexity is O(log(n)), space complexity is also O(log(n)).

Accepted code:

 1 // 3RE, 1WA, 1AC
 2 class Solution {
 3 public:
 4     double pow(double x, int n) {
 5         // IMPORTANT: Please reset any member data you declared, as
 6         // the same Solution instance will be reused for each test case.
 7         if(x == 0.0){
 8             return 0;
 9         }
10         
11         // 1RE here, special case of x = 1
12         if(x == 1.0){
13             return 1.0;
14         }
15         
16         // 1RE, special case of x < 0
17         if(x < 0){
18             if(n % 2 == 1){
19                 return -pow(-x, n);
20             }else{
21                 return pow(-x, n);
22             }
23         }
24         
25         // 1RE, should be $n, wrote $x
26         if(n < 0){
27             return pow(1.0 / x, -n);
28         }else if(n == 0){
29             return 1.0;
30         }else if(n == 1){
31             return x;
32         }else{
33             if(n % 2 == 1){
34                 // 1WA here, pow(x * x, n / 2) is wrong
35                 double res = pow(x, n / 2);
36                 return x * res * res;
37             }else{
38                 double res = pow(x, n / 2);
39                 return res * res;
40             }
41         }
42     }
43 };