CODEWITHSUNDEEP
pythonlargenumberperfect-square
titan7585
titan7585

Reputation: 300

How to find perfect squares in a range efficiently when the inputs are large numbers in Python

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)

Upvotes: 4

Views: 3742

Answers (3)

Stefan Gruenwald
Stefan Gruenwald

Reputation: 2640

There are several mistakes in your code, like numbers = map(int, raw_input().split()) has to be outside of the loop. Same with counter=0. Anyway, here is a code for you that should work for even really high integer numbers:

t = map(int,raw_input().split())

def is_perfect_square(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return False
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

count = 0
for i in t:
    if is_perfect_square(i)**2 == i:
        count+=1

print count

Upvotes: 0

Hackaholic
Hackaholic

Reputation: 19753

this is what i have tried:

>>> def isperferct_square(n):
...     return int(math.sqrt(n))*int(math.sqrt(n)) == n
... 
>>> isperferct_square(10)
False
>>> isperferct_square(9)
True
>>> isperferct_square(10000000000000000000)
False
>>> isperferct_square(112312424354957359732985732897583297592735932)
False
>>> isperferct_square(10000000000)
True
>>>

Upvotes: 0

arshajii
arshajii

Reputation: 129537

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

Upvotes: 9

Related Questions