ऐरे जिसमें किसी भी सबसेट का GCD दिए गए ऐरे से संबंधित हो

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

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

एल्गोरिदम

generateArray(arr, n)

शुरुआत
    answer := खाली ऐरे
    gcd := ऐरे arr का gcd
    यदि gcd, arr के न्यूनतम तत्व के समान है, तो
        arr में प्रत्येक तत्व e के लिए करें
            answer में gcd जोड़ें
            answer में e जोड़ें
        पूर्ण
        answer प्रदर्शित करें
    अन्यथा
        ऐरे नहीं बनाया जा सकता
    यदि समाप्त
समाप्त

उदाहरण

#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]) {
        answer.push_back(arr[0]);
        for (int i = 1; i < arr.size(); i++) {
            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);
    return 0;
}

आउटपुट

2 2 4 2 6 2 12