The problem “Fun game” from a competition

Question

I recently began to learn Python and encountered this problem.

The condition:
You and your friends are playing the next game. Friends write 𝑁 natural numbers in a row on the board. Your task is to find as many consecutive numbers as possible that are divisible by the same number greater than 1. Since it is difficult to find the answer manually, you decided to write a program that will do the job for you.

Input:
The first line of the input contains the number 𝑁 (1 ≤ 𝑁 ≤ 100000). The second line is separated by a space 𝑁 integers 𝐴1...𝐴 𝑁(1 ≤ 𝐴𝑖 ≤ 1000, 1 ≤ 𝑖 ≤ 𝑁). These are the numbers that your friends wrote. They are given in the same order as they are placed on the board.

Output:
Your program should output a single integer — the largest number of consecutive numbers in a given sequence that would be divisible by the same natural number greater than 1.

Here is my code:

Python
    
from math import gcd

def func(n,a):

    mx = 0
    for i, cur_g in enumerate(a):
        if n - i < mx:
            break
        p = 0
        for j in range(i, n):
            cur_g = gcd(cur_g, a[j])
            if cur_g == 1:
                break
            p += 1
            if mx < p:
                mx = p

    return mx

print(func(int(input()), [int(i) for i in input().split()]))

The problem is that I can't pass the time check: the program runs for longer than 0.5 seconds. And I can't think of any way to speed up the program. It may even be necessary to solve the problem itself in a different way. Please help me. Thanks in advance!

Answer 1

The way your loops are organized results in an unpleasant phenomenon. Namely, you process the same subsequence many times. Let's say, a long good range starts at the index k and has a length n. The inner loop finds it. Then the next iteration of the outer loop starts processing it again, this time from index k + 1. Then from index k+2, etc. It will take \$O(n^2)\$ of unnecessary computations. In fact, each good range contributes a term quadratic to its length to the total complexity.

The fix is, once the inner loop terminated, adjust i to continue from the number which broke the good range.