69. Sqrt(x)

Intuition

We are asked to compute the square root of a non-negative integer x, rounded down to the nearest integer, without using any built-in functions. Since the square root function is monotonically increasing, we can use binary search to efficiently find the answer.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

public int mySqrt(int number) {
    if (number == 0) return 0; // Edge case for 0

    int left = 1, right = number;
    int squareRootFloor = 0; // Store the answer (floor of actual square root)

    while (left <= right) {
        // Avoid overflow with (right - left) / 2 + left
        int mid = (right - left) / 2 + left;

        long square = (long) mid * mid;

        if (square == number) {
            return mid; // Perfect square case
        }

        if (square < number) {
            squareRootFloor = mid;  // Store the closest value so far
            left = mid + 1;         // Try to find a larger valid sqrt
        } else {
            right = mid - 1;        // Search in the smaller half
        }
    }

    return squareRootFloor; // Return floor of sqrt
}