It is always easy to calculate a square root using math method. We know that square root of 4 equals to 2, square root of 9 equals to 3 and so on. But what if we are going to do it in programming way?

Sure, we could use the default library function such as Math.sqrt(x) like that, it does help us to get the square root of whatever number we put into the function, but this is not the point of implementing the function natively.

So now, assume that we need to implement a function that is identical to native library function Math.sqrt(x), except that when the number is not perfect square root number, we return its previous square root number.

Without further ado, let's get to the code:

public int sqrt(int x){
    if(x == 0 || x == 1){
        return x;
    }

    int start = 1, end = Integer.MAX_VALUE;

    while (start + 1 < end){
        int mid = start + (end - start) / 2;
        if(mid == x/mid){
            return mid;
        } else if(mid > x/mid){
            end = mid;
        } else{
            start = mid;
        }
    }      
    return start;
}

That's it! Did you notice that I am using while(start + 1 < end) template to solve binary search related problems? Well, I will write a post to talk about how easy and beatiful it is to use this template to solve those problems.

One thing that has to bear in mind is that whenever we need to perform some evaluation such as x * 10 == y, do not use multiplication for that, we use division instead, like x == y / 10. Reason being, it might actually cause the integer to be overflowed when doing multiplication, doing division won't cauaw any sort of overflowing scenarios.

That's all for now! Adios!

Post was published on 3 Mar 2019, last updated on 3 Mar 2019.

Like the content? Support the author by paypal.me!