package com.freetymekiyan.algorithms.level.medium;

/**
 * Implement pow(x, n).
 * <p>
 * Company Tags: LinkedIn, Google, Bloomberg, Facebook
 * Tags: Binary Search, Math
 * Similar Problems: (M) Sqrt(x), (M) Super Pow
 */
public class Pow {

    /**
     * Binary Search. Math.
     * Decompose the exponent into powers of 2, so that you can keep dividing the problem in half.
     * N = 9 = 2^3 + 2^0 = 1001 in binary. Then: x^9 = x^(2^3) * x^(2^0).
     * Every time we encounter a 1 in the binary representation of N, multiply the answer with x^(2^i).
     * To handle N = Integer.MIN_VALUE, use a long (64-bit) variable.
     */
    public double myPow(double x, int n) {
        double ans = 1; // Might be a fraction.
        long absN = Math.abs((long) n); // Must convert n to long first to avoid overflow.
        while (absN > 0) {
            if ((absN & 1) == 1) {
                ans *= x;
            }
            // Update absN and x for the next loop/digit.
            absN >>= 1;
            x *= x; // x^(2^N) -> x^(2^(N+1))
        }
        return n < 0 ? 1 / ans : ans; // Deal with negative.
    }
}

@@ -49,16 +49,40 @@
 m;%0A%0A/**%0A
+ * 50. Pow(x, n)%0A * %3Cp%3E%0A
  * Imple
@@ -894,16 +894,37 @@
  == 1) %7B
+ // Check lowest bit.
 %0A       
@@ -972,77 +972,41 @@
     
-// Update absN and x for the next loop/digit.%0A            absN %3E%3E= 1;
+absN %3E%3E= 1; // Right shift a bit.
 %0A   
@@ -1047,16 +1047,17 @@
 2%5E(N+1))
+.
 %0A       
@@ -1115,15 +1115,12 @@
 th n
-egative
+ %3C 0
 .%0A  
@@ -1124,9 +1124,8 @@
 %0A    %7D%0A%7D
-%0A

update 50. Pow(x, n)