Sqrt(x)

In the problem statement, it is mentioned that we cannot use any inbuilt functions, and in case if the answer has decimals we will need to round it down to nearest integer. so in this approach, what we will do is using 1 and x as left and right boundaries, we will apply Binary Search algorithm.

We will compute the mid element and then calculates its square, based on this value we can draw three conclusions.

• If the square value is equal to x, then return the mid value.
• If the square value is greater than x, this means that the target lies on left side, so we will update right value to mid-1.
• If the square value is less than x, this means that the target lies on right side, so we will update left value to mid+1.

If the answer is not found, we will return right value, because when the square value is greater than x we will adjust it to mid-1, so it already have nearest lower bound integer.

public class Sqrt {

    static int mySqrt(int x) {
        int left = 1;
        int right = x;
        while(left <= right) {
            int mid = left + (right - left) /2;
            long square = (long)mid * mid;
            if(square == x) {
                return mid;
            } else if(square > x) {
                right = mid -1;
            } else {
                left = mid+1;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(4));
        System.out.println(mySqrt(8));
        System.out.println(mySqrt(2147395599));
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input number x.
Space complexity: O(1).