# Remove an element to maximize the GCD of a given array

**Problem**

You are given an array, let's call it **arr []** of lenght **N >= 2**. Your task to remove any one element from the array, so that, **GCD** of whole array is maximized.

**Sample Example**

**Input**

`12 15 18`

**Output**

`6`

**Explanation**

Here we have 12, 15 and 18 as elements of array, from input. We have to remove any element from array to maximize its GCD.

To start with, let's remove 12 first.

GCD(15,18) = 3

Now, Let's remove 15.

GCD(12,18) = 6

Let's check by removing 18.

GCD(12,15) = 3

Here, we clearly see GCD(12,18) = 6 is the maximum we can obtain.

**Solution**

**Geneal idea**

Since we have to remove only 1 element, what we can do is, we'll generate all possible sub-sequences of size **N-1** of this array and find their **GCD**, after that, the maximum value of GCD would be our answer.

We can do that for sure. But this is very inefficient, once the size of array gets big, this apporach will be very slow.

**Optimal approach to find GCD of sub-sequences**

We'll use **single state dynamic programming**.

we'll create 2 arrays, **prefixGCD [ ]** and **sufficGCD [ ]**.

Then** GCD(prefixGCD[i – 1], suffixGCD[i + 1]) **will be our required answer.

Let's code this idea.

```
#include <bits/stdc++.h>
using namespace std;
int MaxGCD(int a[], int n)
{
// returns max GCD after removing an element
// Prefix and Suffix arrays
int Prefix[n + 2];
int Suffix[n + 2];
// Single state dynamic programming relation to store gcd of first i elements
// from left in Prefix[i]
Prefix[1] = a[0];
for (int i = 2; i <= n; i += 1) {
Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]);
}
// Initializing Suffix array
Suffix[n] = a[n - 1];
// Single state dynamic programming relation
// for storing gcd of all the elements having
// greater than or equal to i in Suffix[i]
for (int i = n - 1; i >= 1; i -= 1) {
Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]);
}
// If first or last element of
// the array has to be removed
int ans = max(Suffix[2], Prefix[n - 1]);
// If any other element is replaced
for (int i = 2; i < n; i += 1) {
ans = max(ans, __gcd(Prefix[i - 1], Suffix[i + 1]));
}
// Return the maximized gcd
return ans;
}
int main()
{
int a[100];
int n;
// get the total number of elements
cin>>n;
// get input to all elements
for(int i=0; i<n; i++)
{
cin>>a[i];
}
cout << MaxGCD(a, n);
return 0;
}
```