Generate an array where every subarray GCD is in the given array

Generate an array A, such that gcd of all its contiguous subarray is present in the given array G. If it is not possible to generate such an array then print -1.

Examples :

Input : 4 12 16 20 Output : 4 4 12 4 16 4 20 Input : 2 4 6 12 Output : 4 6 12

Approach :

1. If the minimum element in the array G is not the GCD of the array G then it is not possible to generate such an array.
2. Otherwise, we have to insert the minimum element between every two consecutive element of the array G.

Implementation :

// Generate an array A such that gcd of all its 
// contiguous subarray is present in the given array G.
#include<bits/stdc++.h>
using namespace std;

// Function to generate an array A such that gcd of all its  
// contiguous subarray is present in the given array G.
void generateArray(int G[],int n)
{
    // Finding the minimum element
    int small = *min_element(G , G + n);
    
    int flag = 0;
    
    // Looping through the array
    for (int i = 0; i < n; i++)
    {
        // Check if small divides each element of G
        if (G[i] % small != 0)
        {
            flag=1;
            break;
        }
    }
    
    // Such an array is not possible
    if (flag)
    {
        cout << -1;
    }
    // Print the required array
    else
    {
        cout << G[0] << " ";
        
        for (int i = 1; i < n; i++)
            cout << small << " " << G[i] << " ";
        
    }
    
}

int main(){
    // Initialize the array
	int G[]={20, 5, 25, 15};
	
	// Length of the array
    int n = sizeof(G) / sizeof(G[0]);
    
    // Function to print the array 
	generateArray(G, n);
	
	return 0;
}