package com.fishercoder.solutions;

/**
 * 50. Pow(x, n)
 *
 * Implement pow(x, n).

 Example 1:

 Input: 2.00000, 10
 Output: 1024.00000

 Example 2:

 Input: 2.10000, 3
 Output: 9.26100
 */
public class _50 {

  public static class Solution1 {
    /**
     * Time: O(logn)
     * Space: O(logn)
     */
    public double myPow(double x, int n) {
      long N = n;
      if (N < 0) {
        x = 1 / x;
        N = -N;
      }
      return fastPow(x, N);
    }

    private double fastPow(double x, long n) {
      if (n == 0) {
        return 1.0;
      }
      double half = fastPow(x, n / 2);
      if (n % 2 == 0) {
        return half * half;
      } else {
        return half * half * x;
      }
    }
  }

  public static class Solution2 {
    /**
     * Time: O(logn)
     * Space: O(1)
     */
    public double myPow(double x, int n) {
      long N = n;
      if (N < 0) {
        x = 1 / x;
        N = -N;
      }
      double answer = 1;
      double currentProduct = x;
      for (long i = N; i > 0; i /= 2) {
        if (i % 2 == 1) {
          answer = answer * currentProduct;
        }
        currentProduct *= currentProduct;
      }
      return answer;
    }
  }
}

@@ -33,164 +33,8 @@
 s;%0A%0A
-/**%0A * 50. Pow(x, n)%0A *%0A * Implement pow(x, n).%0A%0A Example 1:%0A%0A Input: 2.00000, 10%0A Output: 1024.00000%0A%0A Example 2:%0A%0A Input: 2.10000, 3%0A Output: 9.26100%0A */%0A
 publ
@@ -47,24 +47,26 @@
 ss _50 %7B%0A%0A  
+ 
+ 
 public stati
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     /**%0A
@@ -94,32 +94,36 @@
        /**%0A     
+  
+  
 * Time: O(logn)%0A
@@ -114,32 +114,36 @@
 * Time: O(logn)%0A
+    
      * Space: O(
@@ -149,27 +149,35 @@
 (logn)%0A     
-*/%0A
+    */%0A    
     public d
@@ -205,32 +205,38 @@
  int n) %7B%0A      
+     
+ 
 long N = n;%0A    
@@ -223,32 +223,38 @@
     long N = n;%0A
+      
       if (N %3C 0)
@@ -256,32 +256,40 @@
  %3C 0) %7B%0A        
+      
+  
 x = 1 / x;%0A     
@@ -283,32 +283,40 @@
  1 / x;%0A        
+     
+   
 N = -N;%0A      %7D%0A
@@ -305,34 +305,46 @@
   N = -N;%0A      
+   
-%7D%0A
+   %7D%0A      
       return fas
@@ -355,16 +355,20 @@
 (x, N);%0A
+    
     %7D%0A%0A 
@@ -370,16 +370,20 @@
  %7D%0A%0A    
+ 
+   
 private 
@@ -413,24 +413,30 @@
 , long n) %7B%0A
+      
       if (n 
@@ -447,24 +447,32 @@
 ) %7B%0A        
+    
+    
 return 1.0;%0A
@@ -473,32 +473,44 @@
  1.0;%0A      
-%7D%0A
+      %7D%0A   
       
+   
 double half 
@@ -530,16 +530,22 @@
 n / 2);%0A
+      
       if
@@ -560,32 +560,40 @@
 == 0) %7B%0A        
+    
+    
 return half * ha
@@ -596,16 +596,22 @@
 * half;%0A
+      
       %7D 
@@ -617,32 +617,40 @@
  else %7B%0A        
+   
+     
 return half * ha
@@ -667,21 +667,35 @@
     
-%7D%0A
+      %7D%0A  
     
+  
 %7D%0A  
+ 
+ 
 %7D%0A%0A
+  
   pu
@@ -724,16 +724,20 @@
 tion2 %7B%0A
+    
     /**%0A
@@ -737,24 +737,28 @@
    /**%0A     
+   
+ 
 * Time: O(lo
@@ -762,24 +762,28 @@
 (logn)%0A     
+    
 * Space: O(1
@@ -785,27 +785,35 @@
 : O(1)%0A     
+  
+  
 */%0A
+    
     public d
@@ -839,24 +839,30 @@
 x, int n) %7B%0A
+      
       long N
@@ -869,24 +869,30 @@
  = n;%0A      
+ 
+     
 if (N %3C 0) %7B
@@ -892,32 +892,40 @@
  %3C 0) %7B%0A        
+ 
+       
 x = 1 / x;%0A     
@@ -919,32 +919,40 @@
  1 / x;%0A        
+      
+  
 N = -N;%0A      %7D%0A
@@ -949,24 +949,30 @@
 ;%0A      
+     
+ 
 %7D%0A      
 double a
@@ -959,24 +959,30 @@
     %7D%0A      
+     
+ 
 double answe
@@ -988,16 +988,22 @@
 er = 1;%0A
+      
       do
@@ -1023,24 +1023,30 @@
 roduct = x;%0A
+      
       for (l
@@ -1069,24 +1069,32 @@
 ; i /= 2) %7B%0A
+        
         if (
@@ -1103,24 +1103,34 @@
 %25 2 == 1) %7B%0A
+          
           an
@@ -1157,24 +1157,32 @@
 entProduct;%0A
+        
         %7D%0A  
@@ -1171,32 +1171,40 @@
               %7D%0A
+        
         currentP
@@ -1231,26 +1231,38 @@
 duct;%0A      
+     
+ 
 %7D%0A
+      
       return
@@ -1274,16 +1274,22 @@
 er;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 50