Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सरणी से न्यूनतम हटाकर GCD को बढ़ाएं

अवधारणा

दिए गए N संख्याओं के संबंध में, लक्ष्य संख्याओं के न्यूनतम हटाने को निर्धारित करना है ताकि शेष संख्याओं का GCD N संख्याओं के प्रारंभिक GCD से बड़ा हो। यदि GCD को बढ़ाना असंभव है, तो "NO" प्रिंट करें।

उदाहरण

इनपुट

b[] = {1, 2, 4}

आउटपुट

1

पहला तत्व हटाने के बाद, नया GCD 2 है, जो प्रारंभिक GCD यानी 1 से बड़ा है।

इनपुट

b[] = {6, 9, 15, 30}

आउटपुट

3

प्रारंभिक gcd 3 है, 6 और 9 को हटाकर 15 का gcd प्राप्त करें जो 3 से बड़ा है। हम 9 और 15 को हटाकर 6 का gcd भी प्राप्त कर सकते हैं।

विधि

  • यूक्लिडियन एल्गोरिदम का उपयोग करके N संख्याओं का gcd खोजें।
  • सभी संख्याओं को निर्धारित gcd से विभाजित करें।
  • कई क्वेरी के लिए अभाज्य गुणनखंड तकनीक का उपयोग करके, प्रत्येक संख्या का अभाज्य गुणनखंड O(log N) में निर्धारित करें।
  • इस विधि से प्राप्त अभाज्य गुणनखंडों में डुप्लिकेट को खत्म करने के लिए सभी अभाज्य गुणनखंडों को सेट में डालें।
  • हैश-मैप दृष्टिकोण का उपयोग करके, प्रत्येक i-वें तत्व में अभाज्य गुणनखंडों की आवृत्तियों की गणना करें।
  • जब संख्याओं का गुणनखंड किया जा चुका हो, और गिनती आवृत्ति तालिका में संग्रहीत हो, तो हैश-मैप में पुनरावृति करें और उस अभाज्य गुणनखंड को ढूंढें जो सबसे अधिक बार आता है। यह अभाज्य गुणनखंड N नहीं हो सकता, क्योंकि हमने सरणी तत्वों को प्रारंभ में N संख्याओं के प्रारंभिक gcd से विभाजित किया है।
  • परिणामस्वरूप, हटाने की संख्या हमेशा N-(hash[prime_factor]) होगी यदि प्रारंभिक gcd के विभाजन के बाद ऐसे कोई गुणनखंड हैं।

C++ कार्यान्वयन

// C++ program to find minimum removals so that gcd of remaining numbers is more than initial gcd
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001

int spf1[MAXN];

void sieve1(){
    spf1[1] = 1;
    for (int i = 2; i < MAXN; i++)
        spf1[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        spf1[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        if (spf1[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (spf1[j] == j)
                    spf1[j] = i;
        }
    }
}

vector<int> getFactorization1(int x){
    vector<int> ret;
    while (x != 1) {
        ret.push_back(spf1[x]);
        x = x / spf1[x];
    }
    return ret;
}

int minimumRemovals1(int a1[], int n){
    int g = 0;
    for (int i = 0; i < n; i++)
        g = __gcd(a1[i], g);
    unordered_map<int, int> mpp;
    for (int i = 0; i < n; i++)
        a1[i] = a1[i] / g;
    for (int i = 0; i < n; i++) {
        vector<int> p = getFactorization1(a1[i]);
        set<int> s1;
        for (int j = 0; j < p.size(); j++)
            s1.insert(p[j]);
        for (auto it = s1.begin(); it != s1.end(); it++) {
            int el = *it;
            mpp[el] += 1;
        }
    }
    int mini = INT_MAX;
    for (auto it = mpp.begin(); it != mpp.end(); it++) {
        int fir1 = it->first;
        int sec1 = it->second;
        if ((n - sec1) <= mini)
            mini = n - sec1;
    }
    if (mini != INT_MAX)
        return mini;
    else
        return -1;
}

int main(){
    int a1[] = { 6, 9, 15, 30 };
    int n = sizeof(a1) / sizeof(a1[0]);
    sieve1();
    cout << minimumRemovals1(a1, n);
    return 0;
}

आउटपुट

2
  1. - C++ में को-प्राइम ऐरे बनाने के लिए न्यूनतम इंसर्शन

    इस सेक्शन में हम एक और दिलचस्प समस्या देखेंगे। मान लीजिए हमारे पास N एलिमेंट्स का एक ऐरे है। हमें इस ऐरे को को-प्राइम ऐरे बनाने के लिए न्यूनतम इंटरसेक्शन पॉइंट्स ढूंढने हैं। को-प्राइम ऐरे में हर दो लगातार एलिमेंट्स का gcd 1 होता है। हमें ऐरे भी प्रिंट करना है।मान लीजिए हमारे पास {5, 10, 20} जैसे एलि

  1. - C++ में ऐरे के सभी एलिमेंट्स को समान बनाने के लिए न्यूनतम डिलीट ऑपरेशन्स

    समस्या कथनn एलिमेंट्स का एक ऐरे दिया गया है जैसे कि एलिमेंट्स रिपीट हो सकते हैं। हम ऐरे से किसी भी संख्या में एलिमेंट्स डिलीट कर सकते हैं। कार्य ऐरे को समान बनाने के लिए डिलीट किए जाने वाले एलिमेंट्स की न्यूनतम संख्या ढूंढना है।arr[] = {10, 8, 10, 7, 10, -1, -4, 12}सभी ऐरे एलिमेंट्स को समान बनाने के

  1. - पायथन में ऐरे से न्यूनतम हटाकर GCD बढ़ाएं

    मान लीजिए हमारे पास N संख्याओं की एक सूची है। हमें वह न्यूनतम संख्या ढूंढनी है जिन्हें हटाने के बाद शेष संख्याओं का GCD, मूल N संख्याओं के प्रारंभिक GCD से बड़ा हो जाए। इसलिए, यदि इनपुट [6, 9, 15, 30] है, तो आउटपुट 2 होगा क्योंकि प्रारंभिक GCD 3 है, और 6 और 9 को हटाने के बाद GCD 15 हो जाता है, जो 3