LeetCode Pow(x, n): Binary Search vs Bit Decomposition

Overview

LeetCode Pow(x, n) could be solved both by binary search (recursive way) or bit decomposition (iterative way) useful tricks are given here too.

LeetCode Pow(x, n) Problem

Implement pow(x, n).

Binary Search or Bit Decomposition

(1) Binary Search: This problem could be solved in log(n) time in stead of the obvious time O(n). The recursive formula pow(x, n) = pow(x, n/2) * pow(x, n – n / 2) helps. The following code is accepted by the LeetCode OJ to pass this Pow(x, n) problem:

double bs(double x, int n) {
    if (n == 0) return 1;
    double ret = bs(x, n / 2);
    if (n & 1) 
        return ret * ret * x; 
    else 
        return ret * ret; 
}

double pow(double x, int n) {
    if (abs(x) <= eps) return 0.0;
    if (0 == n) return 1.0;
    if (abs(abs(x) - 1.0) <= eps) {
          if (n & 1) return x;
          else 
              return 1.0;
    }
    double ret = x;
    bool negative = n < 0;
    n = abs(n);
    ret = bs(x, n);    
    if (negative) return 1.0 / ret;
    return ret;
}

(2) Bit Decomposition, this is the key to the iterative solution, the key is that x^n could be decomposed into several ports, for example, x^7=x^(1+2+4)=(x^1)(x^2)(x^4), and x^2=(x^1)(x^1), x^4=(x^2)(x^2) where each part actually corresponds to a ONE bit in the binary representation of n. So this motivates the following method which could also be accepted by LeetCode OJ to pass this Pow(x, n) problem which is very compact and solves this LeetCode problem elegantly:

double pow(double x, int n) {
    if (n < 0) {
        x = 1.0 / x, n = -n;
    }
    double ret = 1.0;
    for (double f = x; n > 0; n >>= 1) {
        if (n & 1) ret *= f; 
        f *= f;
    }
    return ret;
} 

Other Tips and Tricks to Polish Code

  1. use val – 0.0 < eps to test if the base x is equal to zero or not instead of using x == 0
  2. use val » 1 instead of val / 2, that is, use bit operation rather than divide or mod operations to improve efficiency.

  3. be careful about special cases like (though a bit ridiculous):  1.00000, -2147483648      -1.00000, -2147483648
  4. if x = 0 and n = 1, return 1. This depends on different judge, the result of 0^0 is actually undefined in maths.

Summary

LeetCode Pow(x, n) could be solved both by binary search (recursive way) or bit decomposition (iterative way) useful tricks are given here too.

Written on May 6, 2013