package binary_search;

/**
 * Created by gouthamvidyapradhan on 22/05/2017.
 Implement int sqrt(int x).

 Compute and return the square root of x.
 */
public class SqrtX
{
    public static void main(String[] args) throws Exception
    {
        System.out.println(new SqrtX().mySqrt(Integer.MAX_VALUE));
    }

    public int mySqrt(int x)
    {
        int s = 0, e = x;
        long ans = 0L;
        while(s <= e)
        {
            long m = s + (e - s) / 2;
            long prod = m * m;
            if(prod <= x)
            {
                s = (int)(m + 1);
                ans = m;
            }
            else e = (int)m - 1;
        }
        return (int)ans;
    }


}