Finding the Square Root of X (All Approaches – Brute Force to Optimal)

Given a non-negative integer x, find the integer part of its square root without using built-in functions like Math.sqrt().

---

Approaches:

1. Brute Force Approach – O(√x)

Logic:

We check each number from 1 to x and see when i * i > x.

• The integer part of the square root would be the largest i such that i * i <= x.

Time Complexity: O(√x)
Space Complexity: O(1)

Code:

public class SqrtBruteForce {
    public static int mySqrt(int x) {
        int i = 0;
        while (i * i <= x && i <= x / 2) {  // Keep multiplying until exceeding x
            i++;
        }
        return i - 1;  // Return the last valid i before exceeding x
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(16));  // Output: 4
        System.out.println(mySqrt(8));   // Output: 2
    }
}

---

2. Binary Search Approach – O(log x)

Logic:

Since the numbers form a sorted sequence (0, 1, 2,...), we can use binary search to find the square root.

1. Start with low = 0 and high = x / 2 (since square roots beyond x/2 won’t exist except for 1 and 0).
2. Find mid, check if mid * mid == x.
3. If mid * mid > x, adjust high. If mid * mid < x, adjust low.

Time Complexity: O(log x)
Space Complexity: O(1)

Code:

public class SqrtBinarySearch {
    public static int mySqrt(int x) {
        if (x == 0 || x == 1) return x;

        int low = 0, high = x / 2, result = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long square = (long) mid * mid;  // Prevent overflow for large x

            if (square == x) {
                return mid;
            } else if (square < x) {
                result = mid;  // Store the last valid mid (floor value)
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(16));  // Output: 4
        System.out.println(mySqrt(8));   // Output: 2
    }
}

---

3. Newton’s Method (Optimal) – O(log x)

Logic:

Newton’s method uses iterative approximation.
To find the square root of x, the equation we want to solve is:
[
f(n) = n^2 – x = 0
]
We can use the Newton-Raphson formula to update the guess n iteratively as:
[
n = n – \frac{f(n)}{f'(n)} = n – \frac{n^2 – x}{2n} = \frac{n + x/n}{2}
]
This formula converges quickly to the square root.

Time Complexity: O(log x) (due to fast convergence)
Space Complexity: O(1)

Code:

public class SqrtNewton {
    public static int mySqrt(int x) {
        if (x == 0) return 0;

        long n = x;  // Start with the initial guess
        while (n * n > x) {
            n = (n + x / n) / 2;  // Apply Newton's formula
        }
        return (int) n;  // Return the integer part of the square root
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(16));  // Output: 4
        System.out.println(mySqrt(8));   // Output: 2
        System.out.println(mySqrt(2147395600));  // Output: 46340
    }
}

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Description
Brute Force	O(√x)	O(1)	Iterates until finding i such that i * i > x.
Binary Search	O(log x)	O(1)	Uses binary search to efficiently narrow down the range.
Newton’s Method	O(log x)	O(1)	Fast convergence using iterative approximation.

---

Best Approach Recommendation:

• For Competitive Programming or Large Inputs: Use Newton’s Method or Binary Search for efficiency (O(log x)).
• For Small Inputs or Simple Needs: Brute force works fine for smaller values of x.