Sqrt(x) Leetcode Solution

As the title says, we need to find the square root of a number. Let say the number is x, then Sqrt(x) is a number such that Sqrt(x) * Sqrt(x) = x. If the square root of a number is some decimal value, then we have to return the floor value of the square root.

Example

4

2

7

2

Approach(Pre-built functions)

The math library of C++ and lang.Math library of Java have the pre-built functions to return the square root of a number. We can apply floor() to avoid any decimal value.

Algorithm

1. If the number is less than 2, return itself
2. Call the sqrt() function
3. Floor the value obtained
4. Print the result

Implementation of Sqrt(x) Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return floor(sqrt(x));
}

int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

Java Program

import java.lang.Math;

class sqrt_x
{
    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return (int)Math.floor(Math.sqrt(x));
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}

2

Complexity Analysis of algorithm to find Sqrt(x)

Time Complexity

O(logN). The sqrt() function uses the Newton-Raphson method to calculate the square root of a number, which has a time complexity of O(logN).

Space complexity

O(1). Constant space is used for variables.

Approach(Binary Search)

Here, we can apply binary search on a range of numbers starting from 1 going up to x / 2where x = given number. Here, we implement the binary search on a chosen sorted sequence instead of an array.

Right limit is set as x / 2 because for every number x, greater than 2, the floor of their square root will be less than x / 2. Depending on the result of the binary search, we can jump to the left or right halves of the original sample space.

Algorithm

1. Create a binarySearch() function returning floor of sqrt(x)
2. Initialize variable ans to store the result
3. If the number is less than 2, return itself
4. Initialise left and right values as 1 and x / 2 respectively
5. Until left <= right:
   • Find middle of this range, mid = left + right / 2
   • In case square of mid is equal to x,  return it as it is the square root
   • If square of mid is less than x, jump to the right half by setting left = mid + 1
   • Otherwise, jump to the left half by setting right = mid – 1 and save this value in ans
6. Print the result

Implementation of Sqrt(x) Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x)
{
    int left = 1 , right = x / 2 , mid , ans;
    long temp;

    while(left <= right)
    {
        mid = (left + (right - left) / 2);
        temp = (long)mid * (long)mid;
        //mid * mid can be large, so use long
        if(temp == x)
            return mid;
        if(temp < x)
            ans = mid , left = mid + 1;
        else
            right = mid - 1;
    }
    return ans;
}

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return binarySearch(x);
}


int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

Java Program

import java.lang.Math;

class sqrt_x
{
    static int binarySearch(int x)
    {
        int left = 1 , right = x / 2 , mid , ans = 0;
        long temp;

        while(left <= right)
        {
            mid = (left + (right - left) / 2);
            temp = (long)mid * (long)mid;
            //mid * mid can be large, so use long
            if(temp == x)
                return mid;
            if(temp < x)
            {
                ans = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ans;
    }

    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return binarySearch(x);
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}

2

Complexity Analysis of algorithm to find Sqrt(x)

Time Complexity

O(logN), as the binary search keeps dividing the sample space to its half. In the worst case, it can make up to logN comparisons.

Space complexity

O(1). Again, constant space is used for variables.