I am trying to solve a problem from Hackerearth. I'm able to solve sample testcases but somehow when I am submitting the solution it gives time limit exceeded error or wrong output message.


Little Dipu is a small kid and like all the other kids, he likes to play, but he plays with numbers (He is extraordinary you know). Now-a-days Dipu has some extra interest in odd numbers. So, he says that a number N is interesting if it has odd number of divisors. Now Dipu turns to you and asks you to tell him how many interesting numbers are there between two given numbers, L and R (both inclusive).


First line of input contains the number of test cases T. Each of the next T lines contains two space separated integers L and R.


For each test case, output an integer, denoting the count of interesting numbers between L and R (both inclusive).

1 <= T <= 100000 
1 <= L <= R <= 1018 
1 3
6 10


In 1st test case, 1 has 1 divisor, 2 has 2 divisors and 3 also has 2 divisors. So only 1 has odd number of divisors. Hence count of interesting numbers is 1.

In 2nd test case, 9 is the only number to have odd number of divisors. So answer is again 1.

My Code:

n = int(input())

for _ in range(n):
    i,j = [int(k) for k in input().split(" ")]

    s = 0
    for l1 in range(i, j):
        count = len([l1 for l2 in range(l1) if l1%(l2+1)==0])

        if count%2 !=0:
            s += 1


How can I improve above code?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.