Leetcode: Square Root

 This question is asked at Microsoft and Amazon.

Here it is: 

Given a non-negative integer x, compute and return the square root of x. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. 

Here are the examples and constraints:

Example 1:

Input: x = 4

Output: 2

Example 2:

Input: x = 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

 

Constraints:

0 <= x <= 2^31 - 1

We try to explore all the integers and use the sort() properties for all the integers. 

First, we might be able to determine the integer square root, which is a^2 <= x < (a + 1)^2, which is integer square root. We can implement an algorithm used by pocket calculators, as follows: 

Here is the algorithm, which is used in calculators:

class Solution {

    public int mySqrt(int x) {

        //0^2 = 0, 1^2 = 1

        if(x < 2) return x;

        //implement the equation and rounding it down

        int left = (int) Math.pow(Math.E, 0.5 * Math.log(x));

        //record things up 

        int right = left + 1;

        //return the greater integer

        return (long) right * right > x ? left : right;

    }

}

The recursion and bit shifts is the most efficient method of computing the square root, and here it is: 

The base case is the same, (x)^1/2 = x for x < 2, so we need to decrease x recursively to go down to the base cases. 

We also use the left and right bit shifts as well. 

The time and space complexity is O(log N), both. 

which returns this algorithm: 

class Solution {

    public int mySqrt(int x) {

        //base case

        if(x < 2) return x; 

        //recursive case

        int left = mySqrt(x >> 2) << 1;

        int right = left + 1;

        //same as above problem

        return (long) right * right > x ? left : right; 

    }

}