IMPLEMENT sqrt(x)


  • 0
    F
    int fSqrt(int x) 
    {    
        // Base cases
        if (x == 0 || x == 1) 
           return x;
     
        // Do Binary Search for floor(sqrt(x))
        int start = 1, end = x, ans;   
        while (start <= end) 
        {        
            int mid = (start + end) / 2;
     
            // If x is a perfect square
            if (mid*mid == x)
                return mid;
     
            // Since we need floor, we update answer when mid*mid is 
            // smaller than x, and move closer to sqrt(x)
            if (mid*mid < x) 
            {
                start = mid + 1;
                ans = mid;
            } 
            else // If mid*mid is greater than x
                end = mid - 1;        
        }
        return ans;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.