এর কোন উপসেটের GCD সহ অ্যারে প্রদত্ত অ্যারের অন্তর্গত?

এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখতে পাব। N উপাদানের একটি সেট আছে। আমাদের এমন একটি অ্যারে তৈরি করতে হবে যাতে সেই অ্যারের যেকোনো উপসেটের GCD উপাদানগুলির প্রদত্ত সেটে থাকে। এবং আরেকটি সীমাবদ্ধতা হল যে জেনারেট করা অ্যারেটি GCD-এর সেটের দৈর্ঘ্যের তিনগুণের বেশি হওয়া উচিত নয়। উদাহরণস্বরূপ, যদি 4টি সংখ্যা থাকে {2, 4, 6, 12}, তাহলে একটি অ্যারে হবে {2, 2, 4, 2, 6, 2, 12}

এই সমস্যা সমাধানের জন্য, আমাদের প্রথমে তালিকাটি সাজাতে হবে, তারপর যদি GCD প্রদত্ত সেটের ন্যূনতম উপাদানের সমান হয় তবে প্রতিটি উপাদানের মধ্যে GCD বসিয়ে অ্যারে তৈরি করুন। অন্যথায়, কোনো অ্যারে তৈরি করা যাবে না৷

অ্যালগরিদম

Array(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