I was solving a problem where I had to determine whether the given number is a Fibonacci number or not.
It involves a step where we have to check if 5*n*n-4 or 5*n*n+4 (n is given number and is always greater than 0) is a perfect square or not. If anyone of those terms or both are perfect squares then it is Fibonacci number else not.
I used the below statements to check for a perfect square.
def isPerfectSquare(n):
x = 5*n**2-4
y = 5*n**2+4
r1 = int(math.sqrt(x))
r2 = int(math.sqrt(y))
return r1*r1==x or r2*r2==y
}
But this method showed wrong answer for 4 of the test cases.
Whereas When I used this(below) method it passed all the test cases.
def isPerfectSquare(n):
r1 = math.sqrt(5*n**2-4)
r2 = math.sqrt(5*n**2+4)
return r1%1==0 or r2%1==0
}
What is the difference between the above two methods in finding a perfect square?
Does it also affect the time complexity of the program?
long long will automatically round up your number so that is why it fails some of the tests try storing the sqrt in a double or long double