увеличить скорость работы кода

Question

задание звучит как:
"Проверьте является ли данное число квадратом какого-то неотрицательного числа."
Нельзя использовать встроенные функции возведения в степень и import
пока мой код выглядит так:

def isPerfectSquare(self, n: int) -> bool:
    if n == 0:
        return True
    else:
        for i in range (int(n/2) + 1):
            if i * i == n:
                return True
        return False

однако, он не проходит лимит по времени, не знаю, как можно сократить затрачиваемое время

Answer 1

Вы можете воспользоваться Итерационной формулой Герона

def sqrt_(a, st): 
    # реализация формулы Герона для нахождения квадратного корня
    x = (st + a/st)/2
    if x==st:
        return x
    return sqrt_(a, x)

def isPerfectSquare(a):
    sq = sqrt_(a, a>>1)
    if sq==int(sq):
        return True
    return False

Пример вызова:
print (isPerfectSquare(50))
Вывод:
False

БЛОГ НА HUSL

увеличить скорость работы кода

Ответы (1 шт):