Square Root of A Non-Negative Integer (Leetcode)

Problem Statement

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Approach

First of all the problem statement says we need to find the square root of a number in an integer format without using a built in function like sqrt().

So, if we think a bit intuitively, we can deduce that square of a number cannot be more than half of that integer.

Now as we know the above given fact, one of the approaches would be iterating over each and every number from 1 till ceil(number / 2). And finding out the num whose square is nearest, yet not more than the given number. This approach would have a time complexity of O(n).

But we might just have a better approach than this using an algorithm popularly known as binary search.

Steps of solving the problem using binary search:

• First of all if the passed number is lower than 0 then return -1, else if its less than or equal to 1 then return the number itself.

• Now take a lower bound of 1 and upper bound as 2 is the number is 2 else ceil(number / 2). Also initiate a sqrt variable with -1 that will keep the track of nearest possible square root.

• After this run a util lower bound <= upper bound.

  • Now find the mid value by using a formula mid = lb + floor((ub - lb) / 2).
  • Check if mid * mid == number and if so set sqrt to mid and break the loop.
  • If the mid * mid < number, we can say that it might be the number that we were searching for so we will set sqrt to mid but we also know that we might find a bigger number whose square could be equal or closer to the given number. So we will set the lb = mid + 1 hence reducing our search area.
  • Else we know that we need to find a smaller number than this and hence we make ub = mid - 1.

• Finally return the sqrt as the square root of the number.

Time complexity of the above given approach is O(log n).

Code

Here we have Typescript to implement the above given approach. But you can obviously use your own favourite language.

function mySqrt(num: number): number {
    if(num < 0 || !Number.isInteger(num)) return -1;

    if(num <= 1) return num;

    let lb = 1;
    let ub = num === 2 ? num : Math.ceil(num / 2);

    let sqrt = -1;

    while(lb <= ub){
        const mid = lb + (Math.floor((ub - lb) / 2));

        if((mid * mid) === num) {
            sqrt = mid;
            break;
        }

        else if ((mid * mid) < num) {
            sqrt = mid;
            lb = mid + 1;
        }

        else ub = mid - 1;
    }

    return sqrt;
}

Result

If you have gained or learned anything from the above given explanation do not forget to give a like ❤️ to the post. Follow me for more such posts and also my social handles are given in my profile, reach me out there.