Monday, May 26, 2014

Leetcode: Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Solution:

public class Solution {
    public int sqrt(int x) {
        if(x <= 0)
            return 0; //Is an error
        int i = 1;
        while(i<Integer.MAX_VALUE/(4*i) && (4*i*i)<x) i*=2;
        
      //Binary search between i and 2*i extended to long to avoid overflow issues
        long begin = i;
        long end = 2 * i;
        while(begin<end)
        {
            long midpoint = (begin + end +1)/2;
            if (midpoint * midpoint == x)
                return (int) midpoint;
            if (midpoint * midpoint < x)
                begin = midpoint;
            else
                end = midpoint-1;
        }
        return (int) begin;
    }
}

No comments :

Post a Comment