Leetcode: Pow

Implement pow(x, n)

First, we want to clarify that n is an integer but can be positive or negative.
Second, this problem has a straight-forward solution:

public double pow(double x, int n)
{
   if(n<0)
      return 1/pow(x,-1*n);
   double solution=1;
   for(int i=0;   i<n; i++)
      solution*=x;
   return solution;
}
This algorithm runs in 0(n) time.
This problems can be solved as using a very simple dynamic programming approach, i.e. we "cache" the result of one operation for future calls.

public double pow(double x, int n)
{
   if(n<0)
      return 1/pow(x,-1*n);

   double y= pow(x,n/2);
   if(n%2==0)   
      return y*y;
   return y*y*x;
}
The ``cache" value is pow(x, n/2).  This is one of the simplest dynamic problems implementations as the cache valued is only used in the same call. This code running time is O(log n)

From here, we only optimize the code so when x takes the value of 1 or -1, we can give the answer directly.

Code:

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