Array with GCD of any of its subset belongs to the given array

Given a set of N elements such that N, task is to generate an array such that the GCD of any subset of the generated array lies in the given set of elements. The generated array should not be more than thrice the length of the set of the GCD.

Prerequisite : GCD of an Array | Subset of Array

Examples :

```Input : 3
1 2 7
Output :  1 1 2 1 7

Input : 4
2 4 6 12
Output : 2 2 4 2 6 2 12

Input : 5
2 5 6 7 11
Output : No array can be build
```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Explanation :
Calculate the GCD of an array or in this case a set. Now, first sort the given set of GCD. If the GCD of this set is equal to the minimum number of the given set, then just by putting this GCD between each number. But, if this GCD is not the minimum element of the given set, then unfortunately “no array can be build”.

C++

 `// C++ implementation to generate the  ` `// required array ` `#include ` `using` `namespace` `std; ` ` `  `// Function to return gcd of a and b ` `int` `gcd(``int` `a, ``int` `b) ` `{ ` `    ``if` `(a == 0) ` `       ``return` `b;        ` `    ``return` `gcd(b % a, a); ` `} ` ` `  `// Function to find gcd of ` `// array of numbers ` `int` `findGCD(vector<``int``> arr, ``int` `n) ` `{ ` `    ``int` `result = arr[0];     ` `    ``for` `(``int` `i = 1; i < n; i++) ` `        ``result = gcd(arr[i], result); ` `    ``return` `result; ` `} ` ` `  `// Function to generate the array ` `// with required constraints. ` `void` `compute(vector<``int``> arr, ``int` `n) ` `{ ` `    ``vector<``int``> answer; ` `     `  `    ``// computing GCD of the given set ` `    ``int` `GCD_of_array = findGCD(arr, n); ` ` `  `    ``// Solution exists if GCD of array is equal ` `    ``// to the minimum element of the array ` `    ``if``(GCD_of_array == arr[0]) ` `    ``{ ` `        ``answer.push_back(arr[0]); ` `        ``for``(``int` `i = 1; i < n; i++) ` `        ``{ ` `            ``answer.push_back(arr[0]); ` `            ``answer.push_back(arr[i]); ` `        ``} ` `     `  `        ``// Printing the built array ` `        ``for` `(``int` `i = 0; i < answer.size(); i++) ` `            ``cout << answer[i] << ``" "``; ` `    ``} ` `    ``else` `        ``cout << ``"No array can be build"``; ` `} ` ` `  `// Driver function ` `int` `main() ` `{ ` ` `  `    ``// Taking in the input and initializing ` `    ``// the set STL set in cpp has a property ` `    ``// that it maintains the elements in ` `    ``// sorted order, thus we do not need  ` `    ``// to sort them externally ` `    ``int` `n = 3; ` `    ``int` `input[]= {2, 5, 6, 7, 11}; ` `    ``set<``int``> GCD(input, input + n); ` `    ``vector<``int``> arr; ` `    ``set<``int``>::iterator it; ` `     `  `    ``for``(it = GCD.begin(); it!= GCD.end(); ++it) ` `        ``arr.push_back(*it); ` ` `  `    ``// Calling the computing function. ` `    ``compute(arr,n); ` `     `  `    ``return` `0; ` `} `

/div>

Java

 `// Java implementation  ` `// to generate the  ` `// required array ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` `// Function to return ` `// gcd of a and b ` `static` `int` `gcd(``int` `a, ` `               ``int` `b) ` `{ ` `    ``if` `(a == ``0``) ` `    ``return` `b;      ` `    ``return` `gcd(b % a, a); ` `} ` ` `  `// Function to find gcd  ` `// of array of numbers ` `public` `static` `int` `findGCD(ArrayList  ` `                                 ``arr, ``int` `n) ` `{ ` `    ``int` `result = arr.get(``0``);  ` `    ``for` `(``int` `i = ``1``; i < n; i++) ` `        ``result = gcd(arr.get(i),  ` `                    ``result); ` `    ``return` `result; ` `} ` ` `  `// Function to generate  ` `// the array with required  ` `// constraints. ` `public` `static` `void` `compute(ArrayList ` `                                  ``arr, ``int` `n) ` `{ ` `    ``ArrayList answer =  ` `                    ``new` `ArrayList(); ` `     `  `    ``// computing GCD of ` `    ``// the given set ` `    ``int` `GCD_of_array = findGCD(arr, n); ` ` `  `    ``// Solution exists if GCD ` `    ``// of array is equal to the  ` `    ``// minimum element of the array ` `    ``if``(GCD_of_array == arr.get(``0``)) ` `    ``{ ` `        ``answer.add(arr.get(``0``)); ` `        ``for``(``int` `i = ``1``; i < n; i++) ` `        ``{ ` `            ``answer.add(arr.get(``0``)); ` `            ``answer.add(arr.get(i)); ` `        ``} ` `     `  `        ``// Printing the  ` `        ``// built array ` `        ``for` `(``int` `i = ``0``;  ` `                 ``i < answer.size(); i++) ` `            ``System.out.print(answer.get(i) + ``" "``); ` `    ``} ` `    ``else` `        ``System.out.print(``"No array "` `+ ` `                      ``"can be build"``); ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{ ` ` `  `    ``// Taking in the input and  ` `    ``// initializing the set STL ` `    ``// set in cpp has a property ` `    ``// that it maintains the  ` `    ``// elements in sorted order,  ` `    ``// thus we do not need to  ` `    ``// sort them externally ` `    ``int` `n = ``3``; ` `    ``Integer input[]= {``2``, ``5``, ``6``, ``7``, ``11``}; ` `    ``HashSet GCD = ``new` `HashSet ` `                        ``(Arrays.asList(input)); ` `    ``ArrayList arr =  ` `                ``new` `ArrayList(); ` `     `  `    ``for` `(``int` `v : GCD) ` `        ``arr.add(v); ` ` `  `    ``// Calling the ` `    ``// computing function. ` `    ``compute(arr, n); ` `} ` `} ` ` `  `// This code is contributed by ` `// Manish Shaw(manishshaw1) `

Python3

 `from` `math ``import` `gcd ` `# Python 3 implementation to generate the  ` `# required array ` ` `  `# Function to find gcd of ` `# array of numbers ` `def` `findGCD(arr, n): ` `    ``result ``=` `arr[``0``]  ` `    ``for` `i ``in` `range``(``1``,n): ` `        ``result ``=` `gcd(arr[i], result) ` `    ``return` `result ` ` `  `# Function to generate the array ` `# with required constraints. ` `def` `compute(arr, n): ` `    ``answer ``=` `[] ` `     `  `    ``# computing GCD of the given set ` `    ``GCD_of_array ``=` `findGCD(arr, n) ` ` `  `    ``# Solution exists if GCD of array is equal ` `    ``# to the minimum element of the array ` `    ``if``(GCD_of_array ``=``=` `arr[``0``]): ` `        ``answer.append(arr[``0``]) ` `        ``for` `i ``in` `range``(``1``,n): ` `            ``answer.append(arr[``0``]) ` `            ``answer.append(arr[i]) ` `     `  `        ``# Printing the built array ` `        ``for` `i ``in` `range``(``len``(answer)): ` `            ``print``(answer[i],end ``=` `" "``) ` ` `  `     `  `    ``else``: ` `        ``print``(``"No array can be build"``) ` ` `  `# Driver function ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``# Taking in the input and initializing ` `    ``# the set STL set in cpp has a property ` `    ``# that it maintains the elements in ` `    ``# sorted order, thus we do not need  ` `    ``# to sort them externally ` `    ``n ``=` `3` `    ``input` `=` `[``2``, ``5``, ``6``, ``7``, ``11``] ` `    ``GCD ``=` `set``() ` `    ``for` `i ``in` `range``(``len``(``input``)): ` `        ``GCD.add(``input``[i]) ` ` `  `    ``arr ``=` `[] ` ` `  `    ``for` `i ``in` `GCD: ` `        ``arr.append(i) ` ` `  `    ``# Calling the computing function. ` `    ``compute(arr,n) ` `     `  `# This code is contributed by ` `# Surendra_Gangwar `

C#

 `// C# implementation  ` `// to generate the  ` `// required array ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `    ``// Function to return ` `    ``// gcd of a and b ` `    ``static` `int` `gcd(``int` `a, ``int` `b) ` `    ``{ ` `        ``if` `(a == 0) ` `        ``return` `b;      ` `        ``return` `gcd(b % a, a); ` `    ``} ` `     `  `    ``// Function to find gcd  ` `    ``// of array of numbers ` `    ``static` `int` `findGCD(List<``int``> arr,  ` `                               ``int` `n) ` `    ``{ ` `        ``int` `result = arr[0];  ` `        ``for` `(``int` `i = 1; i < n; i++) ` `            ``result = gcd(arr[i],  ` `                         ``result); ` `        ``return` `result; ` `    ``} ` `     `  `    ``// Function to generate  ` `    ``// the array with required  ` `    ``// constraints. ` `    ``static` `void` `compute(List<``int``> arr,  ` `                                ``int` `n) ` `    ``{ ` `        ``List<``int``> answer = ``new` `List<``int``>(); ` `         `  `        ``// computing GCD of ` `        ``// the given set ` `        ``int` `GCD_of_array = findGCD(arr, n); ` `     `  `        ``// Solution exists if GCD ` `        ``// of array is equal to the  ` `        ``// minimum element of the array ` `        ``if``(GCD_of_array == arr[0]) ` `        ``{ ` `            ``answer.Add(arr[0]); ` `            ``for``(``int` `i = 1; i < n; i++) ` `            ``{ ` `                ``answer.Add(arr[0]); ` `                ``answer.Add(arr[i]); ` `            ``} ` `         `  `            ``// Printing the  ` `            ``// built array ` `            ``for` `(``int` `i = 0; i < answer.Count; i++) ` `                ``Console.Write(answer[i] + ``" "``); ` `        ``} ` `        ``else` `            ``Console.Write(``"No array "` `+ ` `                          ``"can be build"``); ` `    ``} ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `     `  `        ``// Taking in the input and  ` `        ``// initializing the set STL ` `        ``// set in cpp has a property ` `        ``// that it maintains the  ` `        ``// elements in sorted order,  ` `        ``// thus we do not need to  ` `        ``// sort them externally ` `        ``int` `n = 3; ` `        ``int` `[]input= ``new` `int``[]{2, 5, 6, 7, 11}; ` `        ``HashSet<``int``> GCD = ``new` `HashSet<``int``>(input); ` `        ``List<``int``> arr = ``new` `List<``int``>(); ` `         `  `        ``foreach` `(``int` `b ``in` `GCD) ` `            ``arr.Add(b); ` `     `  `        ``// Calling the ` `        ``// computing function. ` `        ``compute(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by ` `// Manish Shaw(manishshaw1) `

Output:

```No array can be build
```

Time Complexity : O(nlog(n)), where n is the size of array given.