कार्य को देखते हुए किसी दिए गए सरणी Arr[] से N सकारात्मक तत्वों के साथ 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[] चलनी () फ़ंक्शन को कॉल करके एराटोस्थनीज की छलनी का उपयोग करके
-
फ़ंक्शन में MaxSize() i=0 से i
-
फिर i=1 से i
-
फिर सॉर्ट () फ़ंक्शन का उपयोग करके वेक्टर अंतर को सॉर्ट करें।
-
अब i=1 से i
-
असंभव केस के लिए if स्टेटमेंट चेक का उपयोग करना, वह तब होता है जब K=0 और कोई कंपोजिट नहीं होता है।
-
यदि K, कंपोजिट की संख्या से अधिक या उसके बराबर है, तो अतिरिक्त प्राइम सहित सभी कंपोजिट को हटा दें और इष्टतम उत्तर प्राप्त करने के लिए इन उप-सरणी का आकार 1 होना चाहिए, ताकि इष्टतम उत्तर मिल सके
-
यदि K, कंपोजिट की संख्या से कम है, तो हमें उन सब-एरे को हटाना होगा जिनमें कंपोजिट शामिल हैं और प्राइम सब-एरे इस श्रेणी में नहीं आने चाहिए।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
//Sieve of Eratosthenes
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;
//Inserting the indices of composite numbers
for (int i = 0; i < N; i++){
if (prime[arr[i]])
vect.push_back(i);
}
/*Computing the number of prime numbers between
two consecutive composite numbers*/
for (int i = 1; i < vect.size(); i++){
diff.push_back(vect[i] - vect[i - 1] - 1);
}
//Sorting the diff vector
sort(diff.begin(), diff.end());
//Computing the prefix sum of diff vector
for (int i = 1; i < diff.size(); i++){
diff[i] += diff[i - 1];
}
//Impossible case
if (K > N || (K == 0 && vect.size())){
return -1;
}
//Deleting sub-arrays of length 1
else if (vect.size() <= K){
return (N - K);
}
/*Finding the number of primes to be deleted
when deleting the sub-arrays*/
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;
}
}
//Main function
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