Как реализовать isPerfectSquare без Math.sqrt? Альтернативные подходы.

Чтобы проверить, является ли число совершенным квадратом без использования Math.sqrt, можно применить несколько альтернативных подходов:

1. Бинарный поиск:
   • Идея: искать целое число x, такое что x * x == num.
   • Реализация: установить границы от 0 до num, и сужать диапазон, сравнивая квадрат среднего элемента с 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. Метод вычитания последовательных нечетных чисел:
   • Теоретически, сумма последовательных нечетных чисел равна квадрату числа.
   • Вычитаем из num последовательно 1, 3, 5, 7... пока num не станет 0 (совершенный квадрат) или отрицательным (не квадрат).

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

3. Использование методов приближенного вычисления корня (например, метод Ньютона), но без Math.sqrt:
   • Можно реализовать итеративный метод для вычисления корня и проверить, является ли результат целым.

Эти подходы позволяют обойтись без стандартной функции Math.sqrt, при этом сохраняя эффективность и точность.