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

C++ में ठीक k सबएरे हटाकर ऐरे को अभाज्य बनाने पर अधिकतम आकार

दिया गया कार्य N धनात्मक तत्वों वाले दिए गए ऐरे Arr[] से ठीक K सबएरे हटाना है ताकि ऐरे में शेष सभी तत्व अभाज्य हों और शेष ऐरे का आकार अधिकतम हो।

इनपुट

Arr[]={4, 3, 3, 4, 3, 4, 3}, K=2

आउटपुट

3

व्याख्या - K=2, इसका मतलब केवल 2 सबएरे हटाए जाने चाहिए।

हटाए गए सबएरे Arr[0] और Arr[3…5] हैं जो ऐरे Arr[]={3,3,3} छोड़ते हैं जिसमें सभी अभाज्य तत्व हैं और अधिकतम संभव आकार है।

इनपुट

Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2

आउटपुट

3

व्याख्या - हटाए गए सबएरे Arr[1] और Arr[4…6] हैं और शेष अभाज्य ऐरे Arr[]={7,2,11} है।

प्रयुक्त दृष्टिकोण

  • पहले एराटोस्थनीज की छलनी का उपयोग करके सभी अभाज्य संख्याओं को prime[] ऐरे में स्टोर करें sieve() फंक्शन को कॉल करके।

  • MaxSize() फंक्शन में i=0 से i<N तक लूप चलाएं और सभी अभाज्येतर संख्याओं के इंडेक्स नंबर को vect नामक int टाइप के वेक्टर में स्टोर करें।

  • फिर i=1 से i<vect.size तक एक और लूप चलाएं दो लगातार अभाज्येतर संख्याओं के बीच स्थित अभाज्य संख्याओं की संख्या की गणना करने के लिए और इसे diff नामक int टाइप के दूसरे वेक्टर में स्टोर करें।

  • फिर sort() फंक्शन का उपयोग करके diff वेक्टर को सॉर्ट करें।

  • अब i=1 से i<diff.size() तक एक और लूप चलाएं और इस वेक्टर का प्रीफिक्स योग निकालें जो हमें यह जानने में मदद करेगा कि कितनी अभाज्य संख्याओं को हटाने की आवश्यकता है।

  • एक if स्टेटमेंट का उपयोग करके असंभव केस के लिए चेक करें, यानी जब K=0 हो और कोई अभाज्येतर संख्या न हो।

  • यदि K अभाज्येतर संख्याओं की संख्या से बड़ा या बराबर है, तो सभी अभाज्येतर संख्याओं को अतिरिक्त अभाज्य संख्याओं सहित हटा दें और हटाए जाने वाले इन सबएरे का आकार इष्टतम उत्तर प्राप्त करने के लिए 1 होना चाहिए।

  • यदि K अभाज्येतर संख्याओं की संख्या से कम है, तो हमें उन सबएरे को हटाना होगा जिनमें अभाज्येतर संख्याएं हों और अभाज्य सबएरे इस श्रेणी में नहीं आने चाहिए।

C++ प्रोग्राम उदाहरण

#include <bits/stdc++.h>
using namespace std;

const int Num = 1e5;
bool prime[Num];

// एराटोस्थनीज की छलनी
void sieve() {
    for (int i = 2; i < Num; i++) {
        if (!prime[i]) {
            for (int j = i + i; j < Num; j += i) {
                prime[j] = 1;
            }
        }
    }
    prime[1] = 1;
}

int MaxSize(int* arr, int N, int K) {
    vector<int> vect, diff;
    
    // अभाज्येतर संख्याओं के इंडेक्स डालना
    for (int i = 0; i < N; i++) {
        if (prime[arr[i]])
            vect.push_back(i);
    }
    
    /* दो लगातार अभाज्येतर संख्याओं के बीच स्थित अभाज्य संख्याओं की संख्या की गणना */
    for (int i = 1; i < vect.size(); i++) {
        diff.push_back(vect[i] - vect[i - 1] - 1);
    }
    
    // diff वेक्टर को सॉर्ट करना
    sort(diff.begin(), diff.end());
    
    // diff वेक्टर का प्रीफिक्स योग निकालना
    for (int i = 1; i < diff.size(); i++) {
        diff[i] += diff[i - 1];
    }
    
    // असंभव केस
    if (K > N || (K == 0 && vect.size())) {
        return -1;
    }
    
    // लंबाई 1 के सबएरे हटाना
    else if (vect.size() <= K) {
        return (N - K);
    }
    
    /* सबएरे हटाते समय हटाई जाने वाली अभाज्य संख्याओं की संख्या ढूंढना
       जब अभाज्येतर संख्याएं K से अधिक हों */
    else if (vect.size() > K) {
        int tt = vect.size() - K;
        int sum = 0;
        sum += diff[tt - 1];
        int res = N - (vect.size() + sum);
        return res;
    }
}

int main() {
    sieve();
    int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << MaxSize(arr, N, K);
    return 0;
}

आउटपुट

6
  1. C++ में ऐरे में सभी अभाज्य संख्याओं का गुणनफल C++ में ऐरे में सभी अभाज्य संख्याओं का गुणनफल

    कुछ एलिमेंट्स के साथ एक इंटीजर ऐरे arr[] दिया गया है, कार्य उस ऐरे की सभी अभाज्य संख्याओं का गुणनफल निकालना है। अभाज्य संख्याएं वे संख्याएं होती हैं जो या तो 1 से विभाज्य होती हैं या स्वयं संख्या से, या एक अभाज्य संख्या वह संख्या है जो 1 और स्वयं संख्या को छोड़कर किसी अन्य संख्या से विभाज्य नहीं ह

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

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

  1. - C++ में delete[] को ऑपरेंड ऐरे का आकार कैसे पता चलता है

    न्यू ऑपरेटर का उपयोग डायनामिक मेमोरी आवंटन के लिए किया जाता है जो वेरिएबल को हीप मेमोरी पर रखता है। डिलीट[] ऑपरेटर का उपयोग उस मेमोरी को हीप से डीएलोकेट करने के लिए किया जाता है। न्यू ऑपरेटर उन तत्वों की संख्या को मुख्य ब्लॉक में संग्रहीत करता है जो उसने बनाए हैं ताकि डिलीट[] उस संख्या का उपयोग करके