GCD of an array

The size of memory allocated for the segment tree, which represents the tree using an array and maintains the relationship between parent and child indexes, is determined by 2*2 ⌈log₂n⌉ – 1. This method allows for querying the GCD of a given range. Using a segment tree, the preprocessing time is O(n) and the time for a GCD query is O(Logn). The implementation of this method is provided below.


Question:

You have an array A of N integers and Q queries. Each query consists of two integers L and R. Your task is to determine the greatest common divisor of the array after removing the range between L and 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);
}

I obtained
Time Limit Exceeded Error
through this approach. What steps can I take to enhance my algorithm?


Solution:

To optimize the performance for finding the greatest common divisor (gcd) of prefixes and suffixes in an array, you can precompute them separately. The process involves iterating over the array from left to right to store the current gcd for each prefix and from right to left for each suffix. As a result, the time complexity for precomputation is

O(n * log MAX_A)

. When performing a query for a specific

(L, R)

, the number of operations required is

gcd(gcdPrefix[L - 1], gcdSuffix[R + 1]

, making it

O(log MAX_A)

per query. The overall time complexity for all
time complexity
queries is

O((n + q) * log MAX_A)

, which is considered fast.

Frequently Asked Questions