Сложность: 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:
def isPerfectSquare(self, num: int) -> bool:
if num < 2:
return True
x = num // 2
while x * x > num:
x = (x + num // x) // 2
return x * x == num
Ставь 👍 и забирай 📚 Базу знаний