◻️69. Sqrt(x) (easy)

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.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 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.

---

Solutions

Optimised (from PrepInsta)

T.C -> log n

Runtime 0 ms Memory 8.22 MB

Repeat steps until the start pointer becomes greater than the end pointer. At this point, we have found the floor value of the square root, and end holds that value.

// solution from https://prepinsta.com/leetcode-top-100-liked-questions-with-solution/sqrtx/
// Uses binary search to find sq root

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

(From Algo Monster)

Runtime 5 ms Memory 8.26 MB

// Solution from https://algo.monster/liteproblems/69
// Uses binary search to find sq root

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