Leetcode: Pow(x, n)

Implement pow(x, n).

Understand the problem:
This problem looks quite simple at the first glance, however requires considering many corner cases. As defined in the interface, x is a double type, n is int, the return is double. 
Consider when n is negative. 

Naive Solution:
A very straight-forward idea is noticing that x^n equals to x * x * x... x, so we just need to time them up. 

Code (Java):

?

1 2 3 4 5 6 7 8 9

public class Solution {     public double pow(double x, int n) {         double result = 1;         for (int i = 0; i < n; i++) {             result *= x;         }         return result;     } }

Discussion:
The solution has time complexity O(n). It got the TLE error on OJ. Thus we need to figure out a more efficient solution.

A better solution:
We can do it in O(logn) time, think about the reduction operations in logn time. We can do it similar. We can use a recursive solution:

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution {     public double pow(double x, int n) {         if (n < 0) {             return 1 / powHelper(x, -n);         } else {             return powHelper(x, n);         }     }           private double powHelper(double x, int n) {         if (n == 0) return 1;                   double v = powHelper(x, n/2);                   if (n % 2 == 0) {             return v * v;         } else {             return v * v * x;         }     } }

Summary:
This problem is not hard naturally, but the O(logn) solution requires a bit more effort. Do consider recursion when you are found you can divide the problem into smaller problems.