1.
Introduction
1.1.
Sample Example
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Minimize the count of integers to be added in Array to make each adjacent pair co-prime

Urwashi Priya
0 upvote

## Introduction

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

The problem is to minimize 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.

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.

try here

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

``````___________________________________________________________________
___________________________________________________________________
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
___________________________________________________________________``````

## Implementation in C++

``````// C++ code to minimize count of integers to be added in array to make each adjacent pairs co-prime

#include <bits/stdc++.h>
using namespace std;

{
// Sort
sort(arr, arr + n);

// checking for any two adjacent elements being same
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1]) {
return -1;
}
}

int ans = 0;

for (int i = 1; i < n; i++) {
if (__gcd(arr[i], arr[i - 1]) == 1) {
continue;
}

// Check for a single middle element and Maintain a bool value
bool found = 0;

for (int j = arr[i - 1] + 1; j <= arr[i] - 1; j++) {
if (__gcd(arr[i - 1], j) == 1 && __gcd(j, arr[i]) == 1) {
found = 1;
}
}
if (found) {
ans++;
}
else {
ans += 2;
}
}

return ans;
}

int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0; i<N; i++){
cin>>arr[i];
}
}``````

Output:

``````Sample Input:
4
2200 42 2184 17
Sample Output:
3``````

### Complexity Analysis

Time Complexity: O(N*log N + M).

Analysing Time Complexity:

All n elements are traversed once and then log N times. M is the maximum element of the array.

Space complexity: O(1)

## FAQs

1. What is GCD?
The greatest common divisor is the highest common number which divides both the given number.

2. What is __gcd?
This is an inbuilt algorithm in C++ to find the highest common factor of 2 numbers.

3. What is co-prime?
If the gcd of two numbers is 1, then they are said to be co-prime in nature.

## Key Takeaways

This article taught us how to minimize the count of integers to be added in array to make each adjacent pair co-prime by approaching the problem using the modular exponentiation concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could easily take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.

Now, we strongly recommend you practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types.

Happy Coding.

Live masterclass