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

Example

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int getGCDofArray(vector<int> arr) {
   int result = arr[0];
   for (int i = 1; i < arr.size(); i++)
      result = gcd(arr[i], result);
   return result;
}
void generateArray(vector<int> arr) {
   vector<int> 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<int> GCD(data, data + n);
   vector<int> arr;
   set<int>::iterator it;
   for(it = GCD.begin(); it!= GCD.end(); ++it)
      arr.push_back(*it);
   generateArray(arr);
}

Output

2 2 4 2 6 2 12

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!