// Solution runs in O(log n) time and O(log n) space, because it halves search space in half for
// every recursive call.
class Solution {
  public double myPow(double x, int n) {
    if (n == 0) return 1;
    x = (n < 0) ? 1 / x : x;
    long p = Math.abs((long) n);
    return pow(x, p);
  }

  private double pow(double x, long n) {
    if (n == 0) return 1;
    double res = pow(x, n / 2);
    return (n % 2 == 0) ? (res * res) : (res * res * x);
  }
}

@@ -82,20 +82,12 @@
 ace 
-in half 
 for%0A
+
 // e
@@ -379,16 +379,16 @@
 n / 2);%0A
-
     retu
@@ -442,8 +442,430 @@
 ;%0A  %7D%0A%7D%0A
+%0A// Alternative solution%0A// Runs in O(log n) time and O(log n) space, beats 100%25 of submissions.%0Aclass Solution %7B%0A  public double myPow(double x, int n) %7B%0A    return n %3C 0 ? pow(1/x, -((long) n)) : pow(x, (long) n);%0A  %7D%0A%0A  private double pow(double x, long n) %7B%0A    if (n == 0) return 1;%0A    if (n == 1) return x;%0A    long rem = n %25 2;%0A    double res = pow(x, n /2);%0A    return rem == 0 ? res * res : res * res * x;%0A  %7D%0A%7D%0A

add solution