किसी भी उपसमुच्चय के GCD के साथ सरणी दिए गए सरणी से संबंधित है?

यहां हम एक दिलचस्प समस्या देखेंगे। एन तत्वों का एक सेट है। हमें एक सरणी उत्पन्न करनी होगी जैसे कि उस सरणी के किसी भी सबसेट का GCD दिए गए तत्वों के सेट में हो। और एक और बाधा यह है कि उत्पन्न सरणी जीसीडी के सेट की लंबाई के तीन गुना से अधिक नहीं होनी चाहिए। उदाहरण के लिए, यदि 4 संख्याएँ {2, 4, 6, 12} हैं, तो एक सरणी {2, 2, 4, 2, 6, 2, 12}

इस समस्या को हल करने के लिए, हमें पहले सूची को क्रमबद्ध करना होगा, फिर यदि GCD दिए गए सेट के न्यूनतम तत्व के समान है, तो प्रत्येक तत्व के बीच GCD लगाकर केवल सरणी बनाएं। अन्यथा, कोई सरणी नहीं बनाई जा सकती।

एल्गोरिदम

जनरेटअरे(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

उदाहरण

#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);
}

आउटपुट

2 2 4 2 6 2 12