LeetCode Sqrt(x): 4 Methods of Binary Search, Bit Operation and Numeric Ways

Overview

LeetCode Sqrt(x) with 4 methods of binary search, bit operation and numeric analysis ways (Newton’s, Babylonian) are elaborated in detail here.

LeetCode Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution Analysis:  Binary Search, Bit Operation and Numeric Ways

There could be 4 different methods to tackle this LeetCode Sqrt(x) problem: binary search, bit operation and numeric analysis ways (Newton’s, Babylonian). Let’s explore them one by one as follows. For all of the following, keep two important things in your mind:

  1. Note sqrt(2) = 1, sqrt(3) = 1 rather than 2
  2. Note that to avoid overflow, one should rewrite mid * mid < x into mid < x / mid to compare with the input x

Binary search the integer between 1 and x to find the square root. The following code is accepted by LeetCode OJ to pass this Sqrt(x) problem:

int sqrt(int x) {
    if (x <= 1)
        return x;

    int l = 1, r = x, sol, mid;

    while (l <= r) {
        mid = l + (r - l) / 2;
        if (mid <= x / mid) {
            l = mid + 1;
            sol = mid;
        }
        else
            r = mid - 1;
    }
    return sol;
}

2) Bit Operation

Let’s consider this problem from another angle: essentially, we need to find the largest integer ‘s’ such that s * s <= x, since s is an integer, we could just test the each bit of s[0..31]. That is, we try to set s[i] = 1, if doing so makes s^2 > x, then this s[i] bit should be 0, we try all of the 16 least significant bits (Copyright @Sigmainfy)so they are tested and the maximum one is our answer. The following code implemented this idea and could pass the LeetCode OJ for this Sqrt(x) problem.

int sqrt(int x) {
    if (x <= 1)
        return x;
    int res = 0;
    int bit = (1 << 15);

    while (bit) {
        res |= bit;
        if (res > x / res)
            res ^= bit; // set it back
        bit >>= 1;
    }
    return res;
}

3) Numeric Ways

From the other angle of numeric analysis, to find s such that s^2 = x, we need to find the zeros of f(t) = t^2 – x, so we guess an initial value say 1.0 for t and do iterative update of t like using Newton’s iteration or the Babylonia method. The following code is the implementation of Newton’s method and we replace the updating formula with the Babylonia method could give out the code for Babylonia one. Both are consistent using the same framework of code. The following code could pass LeetCode OJ for this Sqrt(x) problem:

double babylonia(double r, double x) {
    return 1 / 2.0  * (r + x / r); ;
}

double newton(double r, double x) {
    return  r - (r * r - x) / (2.0 * r);
}

int sqrt(int x) {
    if (x <= 1)
        return x;

    double r = 1.0;
    double newR = 100;
    double eps = 0.000001;

    while (1) {
        newR = newton(r, x); // or babylogin(r, x);
        if (abs(newR - r) <= eps)
            break;
        r = newR;
    }
    return (int)newR;
}

Summary

LeetCode Sqrt(x) with 4 methods of binary search, bit operation and numeric analysis ways (Newton’s, Babylonian) are elaborated in detail here.

Written on May 6, 2013