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):

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):

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.