/**
 * Implement pow(x, n).
 * 
 * Tags: Math, Binary Search
 */
class Pow {
    public static void main(String[] args) {
        Pow p = new Pow();
        System.out.println(p.pow(2.0, 5));
    }
    
    /**
     * Binary Search, divide n by 2
     * Questions: 
     * 1. can x be zero?
     * 2. can n be negative?
     *
     * When n is odd, multiply result by f
     * f multiply by itself each time
     * Repeat until n == 0
     * x^10 = x^2 * x^8
     * x^9 = x * x^8
     * x^8 = x^8
     * x^7 = x * x^2 * x^4
     * x^6 = x^2 * x^4
     */
    public double pow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) { // neg case
            n = -n;
            x = 1 / x; // x can be zero?
        }
        double res = 1; // mind overflow
        for (double f = x; n > 0; n = n >> 1) { // n >>= 1, n/=2
            if (n % 2 == 1) res *= f;
            f = f * f; // f *= f
        }
        return res;
    }
}

@@ -1,12 +1,64 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A
 /**%0A * Imple
@@ -80,523 +80,550 @@
 %0A * 
+%3Cp%3E
 %0A * 
-Tags: Math, Binary Search%0A */%0Aclass Pow %7B%0A    public static void main(String%5B%5D args) %7B%0A        Pow p = new Pow();%0A        System.out.println(p.pow(2.0, 5));%0A    %7D%0A    %0A    /**%0A     * Binary Search, divide n by 2%0A     * Questions: %0A     * 1. can x be zero?%0A     * 2. can n be negative?%0A     *%0A     * When n is odd, multiply result by f%0A     * f multiply by itself each time%0A     * Repeat until n == 0%0A     * x%5E10 = x%5E2 * x%5E8%0A     * x%5E9 = x * x%5E8%0A     * x%5E8 = x%5E8%0A     * x%5E7 = x * x%5E2 * x%5E4%0A     * x%5E6 = x%5E2 * x%5E4
+Company Tags: LinkedIn, Google, Bloomberg, Facebook%0A * Tags: Binary Search, Math%0A * Similar Problems: (M) Sqrt(x), (M) Super Pow%0A */%0Apublic class Pow %7B%0A%0A    /**%0A     * Binary Search. Math.%0A     * Decompose the exponent into powers of 2, so that you can keep dividing the problem in half.%0A     * N = 9 = 2%5E3 + 2%5E0 = 1001 in binary. Then: x%5E9 = x%5E(2%5E3) * x%5E(2%5E0).%0A     * Every time we encounter a 1 in the binary representation of N, multiply the answer with x%5E(2%5Ei).%0A     * To handle N = Integer.MIN_VALUE, use a long (64-bit) variable.
 %0A   
@@ -645,17 +645,19 @@
  double 
-p
+myP
 ow(doubl
@@ -682,123 +682,200 @@
     
-if (n == 0) return 1;%0A        if (n %3C 0) %7B // neg case%0A            n = -n;%0A            x = 1 / x; // x can be zero?
+double ans = 1; // Might be a fraction.%0A        long absN = Math.abs((long) n); // Must convert n to long first to avoid overflow.%0A        while (absN %3E 0) %7B%0A            if ((absN & 1) == 1) %7B
 %0A   
@@ -879,26 +879,24 @@
         
-%7D%0A
         
 double r
@@ -891,142 +891,112 @@
     
-double re
+an
 s 
+*
 = 
-1; // mind overflow%0A        for (double f = x; n %3E 0; n = n %3E%3E 1) %7B // n %3E%3E= 1, n/=2%0A            if (n %25 2 == 1) res *= f
+x;%0A            %7D%0A            // Update absN and x for the next loop/digit.%0A            absN %3E%3E= 1
 ;%0A  
@@ -1009,58 +1009,112 @@
     
-f = f * f; // f *= f%0A        %7D%0A        return res;
+x *= x; // x%5E(2%5EN) -%3E x%5E(2%5E(N+1))%0A        %7D%0A        return n %3C 0 ? 1 / ans : ans; // Deal with negative.
 %0A   

update pow(x, n)