Time limit exceeded in Python, code to check if a number can be reduced to “1”

I am working on this question:

You are given a number N. You can perform the following operations on N any number of times:

-If N is even, divide N by 2.

-If N is odd, replace N with 3N+1.

Your task is to find out, for a given N, if it is possible to reach the number 1 after performing the above two valid operations on N any number of times.

I tried to implement it with this code written by me:

import math
t=int(input())
for _ in range(t):
    n=int(input())
    check=[]
    while True:
        if(math.log(n,2)%1==0):
            print("YES")
            break
        elif(n in check):
            print("NO")
            break
        else:
            check.append(n)
            if(n==1):
                print("YES")
                break
            elif(n%2==0):
                n=n//2
            else:
                n=(3*n)+1

Here, initially I am checking if the number is a power of 2, because any value which is power of 2 can be reduced to 1. If it is not, I append it to an empty list to check if that number repeats and if the number repeats itself I break out of while loop to print “NO”. In else condition, I have implemented logic according to the question. t is the number of test cases.

I have a test case for which the time limit exceeds and I can’t figure out how to deal with it. This is the number for which time limit exceeds:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111113333333333333333333333333333333333333333333333333333333399999992222222111111111111111111111111111111111232323232323232323232323232323232323232323255555667777777777777788888888888888888818181818181812222222333333333333333333333333333333333333333333333333333333333333333333333333333333333355555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555557777777777777777777777777777777777777777777777777777777777777777777777777777777777777778888888888888888888899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111199999999901111111101111110111111111111122222222200000001111111111111922222222222222222229333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333377777777777777777777777777777777777777777777444444444444400000000999999999999999999999000011111111111111111111111111111111111111111111111111111111111111111111111111111922222222222229999999999666666666666667777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777771111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111119999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999333333333333333333333333333333333333333333337272728293871273187391831731237198239183139173981273917931318273193138139812398139172338218328131831928218781793173818718728179128382781191279719381291821721212102171989181019028127218727810817908729187192187910879128701872987127128871298172287193103981813812381318738138181111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111999999999999999999999999999999999999999999999990000029999999999999999999999999922222222555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555

When I run this code on my local IDE it takes time but returns the correct output, but how should I deal with such test case in a coding platform. Any help would be appreciated.

Answer

First and foremost, please do the appropriate research to learn how to do this more quickly. “Python Collatz” will give you plenty of sources.

As for your particular implementation, you have some unfortunate overhead. For a start, due to floating-point precision problems, your power-of-2 check fails for most exponents above 30. Simply get rid of that; the time you spend looking for powers of 2 is mostly wasted.

Update your code with a much better membership check; try using a set (run a timing experiment on that large integer), and seed the set with a list of integers known to converge to the “black hole” cycle of 4-2-1. You can start with all integers through, say, 10^6. In fact, it’s likely faster to individually check 10,000 numbers before you even start reading input.

Advertisement

Answer