Leet Code Problem - 69 - Sqrt(x) - Difficulty Level : Easy

 Hello All,

Welcome back to another algorithm challenge. Today we are going to look at LeetCode problem number 69 where you need to find square root of input number. Please find below link for detailed statement of problem.

https://leetcode.com/problems/sqrtx/

Now if we read that problem statement , it's given that we can not use pow(x, 0.5) or x ** 0.5.

Now instead of focusing on calculating power root , we will focus on calculating square of number and we try to compare with input weather it matches or not.

If my input greater is less than power we calculated , then again we loop find bigger square value. Now one approach to solve this problem is you start with number 1 and keep calculating square until you reach either equal or greater number than input provided. But this approach will increase my time complexity.

Better approach would to use Binary Search algorithm approach which can give me result in O(logn) time.

Algorithm :

Let's looks at step by step approach how would you solve give problem. Assume you have X=20 as input number to your program , now we know square root of 20 will be always less than or equal to 10. So therefore we define boundary for our search now.

right = 20/2 = 10 << Start from right
left =1 << start from left

Condition >> while (left <= right)

mid = left + (right-left)/2

Once we define boundaries , we will calculate mid value which will  be 6 as shown in above picture. Now we calculate power of 6 which is 36 , 36 is greater that 20 input , so we will shift our right pointer.

right = mid -1;

Now scope for search is reduced. We will repeat process again for new value of left and right then calculate power with input X.

Step 3:

Step 4: This step is final step where we are left with only one number.  Condition left<=right will break here. Return value of right as output.

Another break point will be once we find exact square root , then we will return mid as output of function.

Complete Solution :

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;
      
    long pow;
    int mid, left = 2, right = x / 2;
    while (left <= right) {
      mid = left + (right - left) / 2;
     
      pow = (long)mid * mid;
      if (pow > x) 
          right = mid - 1;
      else if 
          (pow < x) left = mid + 1;
      else 
          return mid;
    }

    return right;
  }
}

Keep learning , Keep Sharing. :)