दिया गया कार्य 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