Сложность: easy
Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.
Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.
Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.
Пример:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
👨💻 Алгоритм:
1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.
2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.
3⃣Если вышли из цикла, вернуть False.
😎 Решение:
class Solution {
public boolean isPerfectSquare(int num) {
if (num < 2) {
return true;
}
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}
}Ставь 👍 и забирай 📚 Базу знаний