5.Sqrt(x)

Implement int sqrt(int x).

Solution I: (Brute Force)

class Solution
{
public:
    int mySqrt(int x)
    {

        unsigned long long int s = 0;
        for (long long int i = 1; i * i <= x; i++)
        {
            s++;
        }
        return s;
    }
};

Time Complexity: O( √n )

Solution II: (Binary Search)

class Solution
{
public:
    int mySqrt(int x)
    {

        if (x == 1)
        {
            return 1;
        }

        int start = 0;
        int end = x;
        long long int ans;
        while (start <= end)
        {

            long long int mid = (start + end) / 2;
            if (mid * mid == x)
            {
                return mid;
            }

            else if (mid * mid < x)
            {
                ans = mid;
                start = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
        return ans;
    }
};

Time Complexity: O(log n)