Does the greatest common divisor of any subset of the array belong to the given array?-C++-php.cn

Does the greatest common divisor of any subset of the array belong to the given array?

Here we will see an interesting question. There is a set containing N elements. We must generate an array such that the GCD of any subset of the array lies within the given set of elements. Another limitation is that the resulting array should not exceed three times the length of the GCD collection. For example, if there are 4 numbers {2, 4, 6, 12}, then an array will be {2, 2, 4, 2, 6, 2, 12}

To solve this problem, we have to First the list is sorted, then if the GCD is the same as the smallest element of the given collection, the array is created by simply placing the GCD between each element. Otherwise the array cannot be formed.

Algorithm

generateArray(arr, n)

Begin answer := empty array gcd := gcd of array arr if gcd is same as the min element of arr, then for each element e in arr, do append gcd into answer append e into answer done display answer else array cannot be formed end if End

Copy after login

Example

#include #include #include using namespace std; int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } int getGCDofArray(vector arr) { int result = arr[0]; for (int i = 1; i < arr.size(); i++) result = gcd(arr[i], result); return result; } void generateArray(vector arr) { vector answer; int GCD_of_array = getGCDofArray(arr); if(GCD_of_array == arr[0]) { //if gcd is same as minimum element answer.push_back(arr[0]); for(int i = 1; i < arr.size(); i++) { //push min before each element answer.push_back(arr[0]); answer.push_back(arr[i]); } for (int i = 0; i < answer.size(); i++) cout << answer[i] << " "; } else cout << "No array can be build"; } int main() { int n = 4; int data[]= {2, 4, 6, 12}; set GCD(data, data + n); vector arr; set::iterator it; for(it = GCD.begin(); it!= GCD.end(); ++it) arr.push_back(*it); generateArray(arr); }

Copy after login

Output

2 2 4 2 6 2 12

Copy after login

The above is the detailed content of Does the greatest common divisor of any subset of the array belong to the given array?. For more information, please follow other related articles on the PHP Chinese website!