SQRT(X)—Square Root Estimation

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , 🎢Floor (Lower Bound) ,🧩Monotonic function

Question

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.

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.

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 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.

Leetcode

Reframing the question

1. What's an sqrt(x)?
1. It is a function for a given value of number x it returns a value of y which if multiplied by iteself gives x (y² or y*y= x).
2. Let's look at some random values of sqrt(x).
1. sqrt(1) = 1
1. 1 * 1 = 1
2. sqrt(2) = 1.41
1. 1.41 * 1.41 = 2
3. sqrt(3) = 1.73
1. 1.73 * 1.73 = 3
4. sqrt(4) = 2
1. 2 * 2 = 4
5. sqrt(8) = 2.82
1. 2.82 * 2.82 = 8

3. We can convert y= sqrt(x) into y² = x or y*y = x. This will allow us to get the value of y. Since we are rounding down we only need whole numbers. We can return the last value of y that is less than or equal to x.
1. We don't need to multiply all the decimals to check if they equal x; the whole numbers will cover the entire range of square roots.
Copy

Rounded Down to 1
1 * 1 = 1
___________________________
1 * 1 = 1
1.41 * 1.41 = 2
1.73 * 1.73 = 3

Rounded Down to 2
__________________________
2 * 2 = 4 

2.236 * 2.236 = 5

2.449 * 2.449 = 6

2.646 * 2.646 = 7

2.828 * 2.828 = 8

Rounded Down to 3
__________________________
3 * 3 = 9
...
...

Brute Force

1. We are going to make guesses from 0 to the x in whole numbers, the last value we find that is less than or equal to x will be our answer.
2. Constraints of the question 0 <= x <= 231 - 1
1. Start of the range—starts from 0
2. End of range—Will use x as the highest possible value since the square root of a number can be equal to itself in the case of 1
3. SQRT(8) = 2, will fit between 2 and 3, and since we are rounding down we return 2

4. SQRT(9) = 3

Implementation

class Solution:
    def mySqrt(self, x: int) -> int:


        if x == 0:
            return 0

        for y in range(1,x+1):
            
            square = y * y

            over = square > x
            under = square < x
            equal = square == x
            
            if over:
                return y - 1 # one before
            elif equal:
                return y
            elif square < x:
                pass

Intuition 2.0

1. As we move from the left to the right of the range, the square root is a 🧩Monotonic function. Once we are past a value of for sqrt(x) we will never come back to that value again for x.



Courtesy: https://www.desmos.com/calculator

2. Since there is a monotonicity, can we solve this problem in logarithmic time by making random guesses for sqrt(8)?

3. We will divide the range into two halves.
1. When we are in the upper half of the range, we will be at a greater value for the square root of x, so the target (square root of x) will be to the left. Therefore, we can eliminate all elements to the right. Similarly, when we are in the lower half of the range, we will be at a smaller value for the square root of x, so the target will be to the right, and we can eliminate all elements to the left.
2. We can include the value equal to the target in the lower half.
4. We hop between each half-chopping element and reduce the range. It will turn out the last element we will chop from the lower half will be our estimated Square root: Largest element before and including the target. This will allow us to return the rounded down value of the target.
5. Turning the problem into a simple 🎢Floor (Lower Bound)

class Solution:

    def floor(self, nums,target):

        left, right = 0, len(nums) - 1
        floor = -1

        while left <= right:

            mid = left + (right - left) // 2

            #True
                # Possible Value

            if nums[mid] <= target :
                floor = mid
                left = mid + 1

						# False
            else: # target < nums[mid]:
                right = mid - 1
        # if not found will return -1  
        return floor

class Solution:
    def mySqrt(self, x: int) -> int:
        
        if x == 0:
            return 0

        left,right = 1,x
        sqrt = 0


        while left <= right:

            mid = left + (right-left)//2
            square = mid * mid

            # True
                # Possible Value
            if square <= x:
                sqrt = mid
                left = mid + 1

            # False
            else: # square > x:
                right = mid - 1


        return sqrt

if square == x:
    return mid

elif square < x:
    sqrt = mid
    left = mid + 1

SandBox PythonTutor (Visualized)

Take Away 🥡

🍦Binary Search(Vanilla) is used to find an index in an array in logarithmic time, but we solved SQRT(x) in logarithmic time, and there was no array in sight. Don’t restrict yourself to thinking about binary search only when you have an array to search. Binary search is far more flexible than that, just think about the monotonic(always increasing/decreasing) nature of the values we are searching in. In this case, we found the value in a function in logarithmic time.

One more thing

As we talked about integer overflow in 🍦Binary Search(Vanilla) there might be an integer overflow case for languages such as java and C++, when doing an operation on large numbers

To prevent the integer overflow

1. mid <= x/mid instead of  square <= x(where square = mid * mid)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition