java - GCD of an array

Question

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive

MY Approach :

public static int gcd(int a ,int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

for(int j = 0; j < Q; j++) {
    int l = in.nextInt();
    int r = in.nextInt();
    ans = 0;
    for(int k = 1; k <= n; k++) {
        if(k < l || k > r) ans = gcd(a[k], ans);
    }
    System.out.println(ans);
}

But This approach give me Time Limit Exceeded Error How can i improve my alogrithm

Answer 1

You can precompute the gcd for each prefix and suffix(let's call it gcdPrefix and gcdSuffix) in O(n * log MAX_A) time(just iterate over your array from left to right and store the current gcd, then do the same thing from right to left). The answer for a (L, R) query is gcd(gcdPrefix[L - 1], gcdSuffix[R + 1])(so it is O(log MAX_A) operations per query). The total time complexity is O((n + q) * log MAX_A). I think it should be fast enough.