This problem is from Codechef January challenge. Click on the link to try this problem on your own.
The problem statement is as follows.
Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R]. The indices start from 1. We have to answer multiple queries of this type.
An obvious solution could be to find the GCD of all the elements from [1,L-1] and [R+1,N] and find the GCD between these two numbers. But this solution is O(n) for each query in the worst case.
First let us pre-process these array to gain some efficiency. Define cumulative GCD as follows.
If A is an array of N elements, the cumulative GCD of an array A from left to right consists of the following.
cgcd[0] = A[0]
cgcd[1] = gcd(cgcd[0], A[1])
cgcd[2] = gcd(cgcd[1], A[2])
…. and so on
Lets create an array fgcd which stores the cumulative GCD from left to right. Also create an array bgcd which stores the cumulative GCD from right to left.
After calculating these values, answering the query is simply finding the GCD of fgcd(L-1) and bgcd(R+1).
Here is the C++ implementation of the above. This each query takes only O(1) time and it takes O(n) extra space to store the pre-processed values.