How can I optimise my code to not get a TLE

help
1

My Solution
I viewed other submissions and they involved printing the GCD*2. How can one come up with that approach? Thank you.

2

The problem statement basically describes the original inefficient subtraction based variant of the Euclidean algorithm. Its performance problems and a required fix are described in the linked wikipedia article:

The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.

I guess, contest participants were supposed to either recognize this algorithm and use a standard library function for GCD or come up with the required optimization on their own.

2 Likes
3
Step 1: refractor your code to make it easier to adjust 
for i in range(int(input())):
    X,Y= map(int,input().split())
    
    while X != Y:
        if(Y > X): # ensure X always contains biggest number
            X, Y = Y, X # single line swap
        if Y == 0:
            break
		
        X = X - Y
        
    print(X + Y)
Step 2: first speedup, we know the solution if Y is a factor of X 
for i in range(int(input())):
    X,Y= map(int,input().split())
    
    while X != Y:
        if(Y > X): # ensure X always contains biggest number
            X, Y = Y, X # single line swap
        if Y == 0:
            break

        if(X%Y == 0):
            X = Y
        else:
            X = X - Y
        
    print(X + Y)
Step 3: second speedup, example, if X is 2 and Y is 99 then we know that we can subtract 2 from 99 multiple (49) times at once. 
for i in range(int(input())):
    X,Y= map(int,input().split())
    
    while X != Y:
        if(Y > X): # ensure X always contains biggest number
            X, Y = Y, X # single line swap
        if Y == 0:
            break
        
        if(X%Y == 0):
            X = Y
        else:
            X = X - (X // Y) * Y # subtract as many times as possible
            # the above line can be rewritten like that:
            # X = X % Y
        
    print(X + Y)

Note: now the code is already fast enough!

Step 4: realize we just wrote code that calculates 2 * gcd

if you don’t find that intuitive, don’t worry. As ssvb mentioned, the Euclidean Algorithm is a good one to know. It is not overly optimized like modern gcd algorithms and not hard to understand.

The Euclidean Algorithm for calculating GCD of two numbers A and B can be given as follows:

  • If A=0 then GCD(A, B)=B since the Greatest Common Divisor of 0 and B is B.

  • If B=0 then GCD(a,b)=a since the Greates Common Divisor of 0 and a is a.

  • Let R be the remainder of dividing A by B assuming A > B. (R = A % B)

  • Find GCD( B, R ) because GCD( A, B ) = GCD( B, R ). Use the above steps again.

1 Like