69. Sqrt(x)

Problem

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. (link)

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and 
since we round it down to the nearest integer, 2 is returned.

Solution

Brute Force Approach

To determine the square root of a number, we begin by examining whether the square of the current number is less than or equal to the target. If so, we store that number and continue until the square exceeds the target. Finally, we return the stored value.

Time - O(n)

Space - O(1)

class Solution {
    public int mySqrt(int x) {
        int ans = 1;
        for(int i=1; i<x; i++){
            if(i*i<=x) 
                ans = i;
            else 
                break;
        }
        return ans;
    }
}

Optimal Approach - Binary Search

We utilize binary search on the potential solutions, employing the standard binary search template. Like the brute force method, we can retain the potential answer in a variable and return it. Alternatively, we can return the value of the high pointer, as initially, the low pointer indicates a valid potential number while the high pointer points to an invalid one. Thus, when the iteration concludes, the high pointer signifies the correct potential answer, and the low pointer indicates an invalid one.

1 2 3 4 5 X X X X X X X
low                    high

Time - O(logn)

Space - O(1)

class Solution {
    public int mySqrt(int x) {
        int low = 1;
        int high = x;

        while(low<=high){
            int mid = (low+high)/2;

            if(mid<=x/mid){
                low = mid +1;
            }
            else{
                high = mid -1;
            }
        }
        return high;
    }
}