def issqr(n): l = 0 u = 1 while n >= u * u: u *= 2 # invariant: sqrt(n) in xrange(l, u) while u - l > 1: m = (l + u) // 2 if n >= m * m: l = m else: u = m return n == l * l
Can you explain the above logic ?one solution is to find the prime factors and if each primary factor is found even number of times then its a perfect square.Or iterate from i=1 to ceil(n/3)and do binary search to find whether i*i == n or not. This will fail only for n=2,so first check for this condition.
def issqr(n):
ReplyDeletel = 0
u = 1
while n >= u * u:
u *= 2
# invariant: sqrt(n) in xrange(l, u)
while u - l > 1:
m = (l + u) // 2
if n >= m * m:
l = m
else:
u = m
return n == l * l
Can you explain the above logic ?
ReplyDeleteone solution is to find the prime factors and if each primary factor is found even number of times then its a perfect square.
Or iterate from i=1 to ceil(n/3)and do binary search to find whether i*i == n or not. This will fail only for n=2,so first check for this condition.