What is the difference between these algorithms for checking for perfect square?

133 Views Asked by At

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?

1

There are 1 best solutions below

0
SzymonO On

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