# GCDQ - Editorial

Author: Praveen Dhinwa
Editorialist: Lalit Kundu

EASY

### PRE-REQUISITES:

GCD, Precomputation

### PROBLEM:

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 (1 Based indexing). You are guaranteed that after excluding the part of the array remaining array is non empty.
1 â‰¤ N, Q â‰¤ 100000

### EXPLANATION:

If you do it naively(ie. calculating GCD of remaining array for each query), the worstcase complexity will be O(N * Q).
Letâ€™s denote by G(L, R), the GCD of AL, AL+1 â€¦ AR. We can observe that for query [L, R], we need GCD of G(1, L-1) and G(R+1, N).
So, we precalculate prefix and suffix gcd arrays.
If we have:
Prefixi = GCD of A1, A2 â€¦ Ai
Suffixi = GCD of AN, AN-1 â€¦ Ai
answer to query [L, R], would be GCD of PrefixL-1 and SuffixR+1.

We can calculate prefix and suffix arrays in O(N) if we notice that:
Prefixi = GCD(Prefixi-1, Ai)
Suffixi = GCD(Suffixi+1, Ai)

Pseudo Code for building prefix and suffix arrays:

``````n,a=input
pre[n],suf[n]

//base case
pre[1]=a[1]
suf[n]=a[n]

for i=2 to n:
pre[i] = gcd(pre[i-1], a[i])

for i=n-1 to 1:
suf[i] = gcd(suf[i+1], a[i])
``````

So, overall complexity would be O((N + Q) * K), where K is a constant factor for gcd calculation.

### ALTERNATIVE SOLUTION:

Use segment trees for range gcd queries. But note that a factor of log N will be increased in complexity.

### SOLUTIONS:

6 Likes

Can anybody see my solution link and tell what is the problem with it. I have used exactly the same technique written here.First I tried using Scanner but resulted in TLE in the second subtask so I switched to BufferedReader method but it keeps on giving the Runtime Error RZEC.

I used segment trees for this one. Now I feel like I shot a fly with a cannon.

6 Likes

Getting a runtime error SIGSEGV

Can anyone please tell me the reason for that?

Code : http://ideone.com/QCJXzv

What is optimal way to calculate GCD of two number Prime factor method or division method or something else ?

```function gcd(a, b)
while b â‰  0
t := b
b := a mod b
a := t
return a
```

this is the pseudo code for euclid algorithm to find the gcd of two number in logarithmic timeâ€¦

you can also use inbuilt function __gcd(a,b) in cpp

here is the cpp implementation of the function

```int gcd(int a,int b){

if(b == 0)
return a ;
else
return gcd(b,a%b)

}
```
1 Like

Why did i get a TLE with exact same solution ?

same here i did the exact same thing and got TLEâ€¦Whats the point of this explanation then??

setterâ€™s and testerâ€™s solution link is not working.

Iâ€™m always getting TLEâ€¦help to optimize the code would be appreciatedâ€¦please tell me what to do. Code Link:http://www.codechef.com/viewsolution/7126221

what should be returned if low and high of segment tree have no overlap with querylow and queryhigh ?
Or
Someone give me a link to the solution using segment tree

why problem is not visible in practice section

If in case someone want segment tree solution in c++. link-https://www.codechef.com/viewsolution/14754012

1 Like

It is okâ€¦ so did I .-.

no problem dude i also thought but constraints let me to drop the idea and i finally formulated the mentioned solution â€¦

Well, your conditions are wrong and its clearly visible:
For example:
if(l==0 && r==n-1)
{
printf(â€ś1\nâ€ť); //how do you know the gcd of entire array is â€ś1â€ť?
}

Now, perhaps you were lucky and before getting WA, some test case made upto this condition which gave you SIGSEGV:
else if(l==0)
{
printf("%d\n",suffix[r+1]); //if r == N, you will access (N+1)th element of array!
}

I didnâ€™t went further into your code after this condition, sorry