🧑‍💻 LeetCode 0069 — Sqrt(x), All Solutions Explained with Java! 🧠

https://github.com/nphausg/leetcode.solution/blob/main/src/com/nphausg/leetcode/utils/sqrt_method_comparison.ipynb

“The journey of a thousand miles begins with one step… or one square root.”

🔍 Problem Overview

Given a non-negative integer x, compute and return the square root of x, rounded down to the nearest integer. You must not use any built-in exponent function or operator like Math.sqrt() or x ** 0.5.

Example:

Input: x = 8
Output: 2
Explanation: sqrt(8) ≈ 2.828, so we return 2.

🛠️ Solution 1: Brute Force (Linear Search) 🐢

Idea

Try all integers i starting from 0. Stop when i * i > x. The previous i will be the answer.

public int mySqrt(int x) {
    if (x < 2) return x;

    for (int i = 1; i <= x / 2; i++) {
        if (i <= x / i && (i + 1) > x / (i + 1)) {
            return i;
        }
    }
    return 1;
}

⏱️ Time Complexity:

• O(√x) — Worst case for very large x.

🗂️ Space Complexity:

• O(1) — Only constant extra space.

⚠️ Drawback:

• Not efficient for very large values of x.

⚡ Solution 2: Binary…