Minimum insertions to make a Co-prime array in C++

In this section we will see another interesting problem. Suppose we have an array of N elements. We have to find minimum number of intersection points to make this array as co-prime array. In the co-prime array gcd of every two consecutive elements is 1. We have to print the array also.

Suppose we have elements like {5, 10, 20}. This is not co-prime array. Now by inserting 1 between 5, 10 and 10, 20, it will be co-prime array. So the array will be like {5, 1, 10, 1, 20}

Algorithm

makeCoPrime(arr, n): begin    count := 0    for i in range 1 to n, do       if gcd of arr[i] and arr[i – 1] is not 1, then increase count by 1    done    display count value    display the first element of arr    for i in range 1 to n, do       if gcd of arr[i] and arr[i – 1] is not 1, then display 1    display element arr[i]    done end

Example

 Live Demo

#include <iostream> #include <algorithm> using namespace std; int makeCoPrime(int arr[], int n){    int count = 0;    for(int i = 1; i<n; i++){       if(__gcd(arr[i], arr[i - 1]) != i){          count++;       }    }    cout << "Number of intersection points: " << count << endl;    cout << arr[0] << " ";    for(int i = 1; i<n; i++){       if(__gcd(arr[i], arr[i - 1]) != i){          cout << 1 << " ";       }       cout << arr[i] << " ";    } } int main() {    int A[] = {2, 7, 28};    int n = sizeof(A)/sizeof(A[0]);    makeCoPrime(A, n); }

Output

Number of intersection points: 1 2 7 1 28