The question is how to find perfect squares in a given range efficiently when the inputs are very large numbers. My solution is giving Time Limit Exceeded error. I have already checked the following links, but they didn't solve my problem:
- Python Program on Perfect Squares
- How could I check if a number is a perfect square?
- Fastest way to determine if an integer's square root is an integer (I have no idea how to implement the solution given in this link in Python).
The problem question is:
Input Format: First line contains T, the number of testcases. T test cases follow, each in a newline. Each testcase contains two space separated integers denoting A and B. Find all the perfect squares in the range A and B (both inclusive).
Example of an input:
2 3 9 17 24
The code I wrote is:
import math
def is_perfect_square(n):
return n % n**0.5 == 0
t = int(raw_input())
for i in range(t):
numbers = map(int, raw_input().split())
count = 0
for j in xrange(numbers[0], numbers[1] + 1): # I also tried range() which gave memory error
if (is_perfect_square(j)):
count = count + 1
print count
While this code is working for smaller numbers, it is giving Time limit exceeded error for large inputs.
(NOTE : gmpy is not an option as the code has to be run on an online compiler which does not have the gmpy module)
Instead of looping from A to B and checking for perfect squares, why not just loop through the integers from sqrt(A) to sqrt(B) and square each, giving you your answer.
For example, let's find the square numbers between 1000 and 2000:
sqrt(1000) = 31.6 --> 32 (need the ceiling here)
sqrt(2000) = 44.7 --> 44 (need the floor here)
Therefore, our answer is:
322 = 1024 332 = 1089 342 = 1156 352 = 1225 362 = 1296 372 = 1369 382 = 1444 392 = 1521 402 = 1600 412 = 1681 422 = 1764 432 = 1849 442 = 1936