The greatest common divisor is the highest common number which divides both the given number.

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

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

Table of contents

Introduction

1.1.

Sample Example

Approach

2.1.

PseudoCode

Implementation in C++

3.1.

Complexity Analysis

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

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

Author Urwashi Priya

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.

⬇

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.

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

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

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;

int MinimumAdditions(int arr[], int n)
{
	// 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];
	}
	cout << MinimumAdditions(arr, N);
}

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

What is GCD?
The greatest common divisor is the highest common number which divides both the given number.
What is __gcd?
This is an inbuilt algorithm in C++ to find the highest common factor of 2 numbers.
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.