How to implement isPerfectSquare without Math.sqrt? Alternative approaches.

To check if a number is a perfect square without using Math.sqrt, you can apply several alternative approaches:

1. Binary Search:
   • Idea: find an integer x such that x * x == num.
   • Implementation: set boundaries from 0 to num, and narrow the range by comparing the square of the middle element with num.

public boolean isPerfectSquare(int num) {
    if (num < 0) return false;
    int left = 0, right = num;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long sq = (long) mid * mid;
        if (sq == num) return true;
        else if (sq < num) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

2. Method of subtracting consecutive odd numbers:
   • Theoretically, the sum of consecutive odd numbers equals the square of a number.
   • Subtract 1, 3, 5, 7... from num sequentially until num becomes 0 (a perfect square) or negative (not a square).

public boolean isPerfectSquare(int num) {
    if (num < 0) return false;
    int i = 1;
    while (num > 0) {
        num -= i;
        i += 2;
    }
    return num == 0;
}

3. Using approximate root calculation methods (e.g., Newton's method), but without Math.sqrt:
   • You can implement an iterative method to compute the root and check if the result is an integer.

These approaches allow you to avoid the standard Math.sqrt function while maintaining efficiency and accuracy.