Problem Description

Given a non-negative integer x, we want to compute and return the square root of x. However, since our return type is integer, we should truncate the decimal part and only return the integer part of the result.

For example, given the integer 8, the square root of 8 is approximately 2.82842. Since we should only return the integer part, our function should return 2 in this case.

Solution Approach

The approach used in the solution is known as binary search, an efficient algorithm for finding an item from a sorted list of items. However, in our case the list of items is implicit - we're using binary search to find the square root of our number x in the range from 1 to x itself.

Let's illustrate this approach with the example where x = 8:

1. We initialize our search range between 1 and x, inclusive.
2. We compute the midpoint of our search range by averaging the endpoints. In this case we would compute (1 + 8) / 2 = 4.
3. We square the midpoint and compare it to x. If it's greater than x, then we know that our square root has to be less than the midpoint, so we update our search range to be from the start to the midpoint. If it's less than or equal to x, then the square root is at least the midpoint, so we update our search range to be from the midpoint to the end.
4. We repeat this process until our search range has been narrowed down to a single number, which is our answer.

In the case where x = 8, this process would look like:

Start range: [1, 8] Midpoint: 4, 4^2 = 16 > 8, so update range to [1, 4] Midpoint: 2, 2^2 = 4 <= 8, so update range to [3, 4] Midpoint: 3, 3^2 = 9 > 8, so update range to [3, 3] Our search range has been narrowed down to a single number, so the answer is 3 - 1 = 2.

Python Solution

1
2python
3class Solution:
4  def mySqrt(self, x):
5    l = 1
6    r = x + 1
7
8    while l < r:
9      m = (l + r) // 2 # compute the midpoint
10      if m * m > x:
11        r = m # update the right endpoint if the midpoint squared is larger than x
12      else:
13        l = m + 1 # update the left endpoint if the midpoint squared is less or equal to x
14
15    return l - 1

Java Solution

1
2java
3public class Solution {
4    public int mySqrt(int x) {
5        long l = 1;
6        long r = x + 1l;
7
8        while (l < r) {
9            long m = (l + r) / 2; 
10            if (m * m > x) {
11                r = m; 
12            } else {
13                l = m + 1;
14            }
15        }
16
17        return (int) (l - 1);
18    }
19}

JavaScript Solution

1
2javascript
3class Solution {
4    mySqrt(x) {
5        let l = 1;
6        let r = x + 1;
7
8        while (l < r) {
9            let m = Math.floor((l + r) / 2);
10            if (m * m > x) {
11                r = m;
12            } else {
13                l = m + 1;
14            }
15        }
16
17        return l - 1;
18    }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int mySqrt(int x) {
6        unsigned l = 1;
7        unsigned r = x + 1u;
8
9        while (l < r) {
10            unsigned m = (l + r) / 2;
11            if (m > x / m)
12                r = m;
13            else
14                l = m + 1;
15        }
16
17        return l - 1;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public int MySqrt(int x) {
5        long l = 1;
6        long r = x + 1L;
7
8        while (l < r) {
9            long m = (l + r) / 2; 
10            if (m * m > x) {
11                r = m;
12            } else {
13                l = m + 1;
14            }
15        }
16
17        return (int) (l - 1);
18    }
19}

In all the solutions above, we first ensure the left variable (l) is initialized to 1 and the right variable (r) is initialized to x + 1. This sets up the boundaries in which we will search for the square root.

In the main while loop, we first calculate the midpoint (m) of the current interval (l,r) and then calculate its square. If the square of the midpoint is greater than the target x, it means that we have overshot the value of the square root, so we readjust our search by modifying our right boundary r.

Conversely, if the square of the midpoint m is less than or equal to x, that means the square root must be to the right of m. We therefore adjust our left boundary l.

We keep adjusting our boundaries (l and r) and halve the interval in every iteration of the loop so as to home in onto the exact integer square root.

Note: In the Java solution, the variables and target integer x are declared as long to allow for perfect square integers up to 2^31 -1 which lies within integer range but it's square does not.

In Javascript, we can use the Math.floor function to perform integer division in Python. In the C++ solution, we adjust the value of the midpoint m to prevent overflow. In C#, the division operation “/” is integer division if both operands are integers.

The time complexity for this algorithm is O(log x), because with each iteration we halve the size of our search. This makes the algorithm very efficient, even for large input numbers.

This algorithm can be implemented in other programming languages using the above logic. The specific language constructs and nuances of each language need to be taken into account for successful implementation.