## Introduction

In this blog, we will discuss a number theory problem asked frequently in Interviews.

The problem is to **m****inimize the count of integers to be added in an array to make each adjacent pair co-prime.**

Say we are given an array of n elements. We need to add a minimum possible number in the array, in such a way as to make all adjacent pairs in the given array co-prime. If such a condition is not possible, we return -1.

### Sample Example

```
Sample Input:
2
17 42
Sample Output:
1
Explanation:
our array has 2 elements.
{7, 42}
On adding 11, {7, 11, 42}
All adjacent elements becomes co-prime. So, our answer would be 1. We found on the addition of 1 element, we get our desired condition.
```

Also see, __Euclid GCD Algorithm__

## Approach

The** approach** to minimize the count of integers to be added in an array to make each adjacent pair co-prime is to first find the greatest common divisor of a number and check if it 1. If the two adjacent numbers are not co-prime, then we take all possible numbers between them and check for their nature. If no such numbers exist, we add two new prime numbers by ourselves and return the number of numbers added.

Sort the given array.

⬇

Check for any two adjacent elements being the same. If such condition exists return -1.

⬇

Start iterating for all elements in an array.

⬇

If two adjacent pairs are already co-prime in nature, continue and move forward.

⬇

If two adjacent pairs are not co-prime in nature, run a loop from that element to the very next element in the given array.

⬇

Take each number and check if it forms co-prime with both left and right numbers. If we succeed in finding a number that forms co-prime with both left and right numbers, increment our answer by 1.

⬇

If we fail to find a number that forms co-prime with both left and right numbers, we introduce two new co-prime numbers with each other, and we increment our answer by 2.

⬇

Return answer.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

Please have a look at the algorithm to minimize the count of integers to be added in the array to make each adjacent pair co-prime, and then again, you must give it a try.

### PseudoCode

```
___________________________________________________________________
Procedure MinimumAdditions(int arr[], int n):
___________________________________________________________________
1. sort(arr, arr + n)
2. For all elements in the given array, check: if (arr[i] == arr[i - 1])
If yes return -1.
3. Run loop from 1 till n:
if (__gcd(arr[i], arr[i - 1]) == 1): continue
4. bool found = 0
5. Run loop from j = arr[i - 1] + 1 to j <= arr[i] - 1
if (__gcd(arr[i - 1], j) == 1 && __gcd(j, arr[i]) == 1): found = 1
6. if (found): ans++;
7. Else: ans += 2;
8. return ans;
end procedure
___________________________________________________________________
```