Problem

Implement int sqrt(int x).

OR

Compute and return the square root of x.

OR

If x is not a perfect square, return floor(sqrt(x)) OR floor(√n)

OR

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.

Note

DO NOT USE SQRT FUNCTION FROM STANDARD LIBRARY such as pow(x, 0.5) or x ** 0.5.

Examples

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.

Solution

Method 1 - Naive or Linear Search

The square root of an integer n always lies between 1 and n. If x is the square root of n, then x * x = n. By checking values of x from 1 to n, we can determine if x * x = n holds. This method is known as linear search. If n is not a perfect square, the value of x will satisfy x * x < n < (x + 1) * (x + 1).

Code

Java
class Solution {

	public int mySqrt(int x) {
		if (x == 0 || x == 1) {
			return x;
		}

		int k = 1;
		// if k*k equals to x then k is the answer
		// if k*k < x<(k+1) * (k+1) then k is the answer
		// It means (k+1) * (k+1) > x , k is the answer
		// As k*k may cause integer overflow convert equation k*k <= x => k <= x/k
		while (k <= x / k) {
			k++;
		}

		return k - 1;
	}
}

Complexity

  • ⏰ Time complexity: O(√x)
  • 🧺 Space complexity: O(1)

Method 2 - Binary Search

Code

Java
class Solution {

	public int mySqrt(int x) {
		if (x == 1 || x == 0) {
			return x;
		}

		int low = 0;
		int high = x;
		int ans = 0;

		while (low <= high) {
			int mid = low + (high - low) / 2;

			if (mid <= x / mid) {
				low = mid + 1;
				ans = mid;
			} else {
				high = mid - 1;
			}
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 3 - Newton Method

The solution builds upon a simplified version of Newton’s Method. Newton’s method employs the tangent equation of an initial guess for a function:

$y = f’(x_n) , (x-x_n) + f(x_n)$

By setting ( y = 0 ) and using the x-coordinate as the next input, we derive the recursive relation:

$x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}$

Given that we are finding the point where ( f(x) = x^2 - S = 0 ), we have: $x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}=x_n-\frac{x_n^2-S}{2x_n}=\frac{1}{2}\left(x_n+\frac{S}{x_n}\right)$

This recursion sequence is known as the Babylonian method, which is essentially a form of initial approximation.

Code

Java
public class Solution {

	public int mySqrt(int x) {
		if (x <= 0) {
			return 0;
		}

		double guess = x;
		double epsilon = 1e-7; // Small value for precision

		// Iteratively improve guess
		while (Math.abs(guess - x / guess) > epsilon) {
			guess = (guess + x / guess) / 2.0;
		}

		return (int) Math.floor(guess); // Return the integer part of the square root
	}
}

Complexity

  • ⏰ Time complexity: O(log(log(x))). In each iteration, we do guess = (guess + x / guess) / 2.0.
    • The number of iterations required for the Babylonian method to converge depends on the desired precision and the value of x.
    • Given that the method has quadratic convergence, it requires roughly O(log(log(x))) iterations to reach a given level of precision.
    • For instance, to re
  • 🧺 Space complexity: O(1)

Dry Run

For x = 8:

  • Initial guess: 8
  • Iterative improvements might be: 4.5, 3.138888, 2.843780, 2.828431, etc., until the difference is less than epsilon.
  • The final guess is approximately 2.828431 after sufficient iterations.
  • The floor value is 2.