সি-তে অ্যারে যেখানে যেকোনো সাবসেটের GCD প্রদত্ত অ্যারেতে থাকে

N উপাদানের একটি সেট দেওয়া আছে। এমন একটি অ্যারে তৈরি করতে হবে যাতে এর যেকোনো সাবসেটের GCD প্রদত্ত সেটের উপাদানগুলোর মধ্যে থাকে। আর তৈরি অ্যারের দৈর্ঘ্য প্রদত্ত সেটের তিগুণ থেকে বেশি হবে না। উদাহরণ: {2,4,6,12} → অ্যারে: {2,2,4,2,6,2,12}

সমাধান: প্রথমে সেটটি সর্ট করুন। যদি পুরো অ্যারের GCD ন্যূনতম উপাদানের সমান হয়, তবে প্রতিটি উপাদানের আগে GCD বসিয়ে অ্যারে তৈরি করুন। অন্যথায় অ্যারে তৈরি সম্ভব নয়।

অ্যালগরিদম

generateArray(arr, n)

Begin answer := empty array gcd := array arr-এর GCD if gcd == arr[0] (min element) then for each e in arr do append gcd, append e 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) { ... } int getGCDofArray(vector<int> arr) { ... } void generateArray(vector<int> arr) { ... } int main() {    int n = 4;    int data[] = {2,4,6,12};    set<int> GCD(data, data+n);    vector<int> arr; ...    generateArray(arr); }

আউটপুট

2 2 4 2 6 2 12