প্রদত্ত কাজটি হল প্রদত্ত অ্যারে 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}।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
প্রথমে সমস্ত প্রাইমগুলিকে অন্য অ্যারে প্রাইম[]-এ সঞ্চয় করুন ইরাটোসথেনিসের চালুনি ব্যবহার করে চালুনি() ফাংশনকে কল করে
-
ফাংশনে MaxSize()i=0 থেকে i
-
তারপর পরপর দুটি কম্পোজিটের মধ্যে থাকা প্রাইমগুলির সংখ্যা গণনা করতে i=1 থেকে i
-
তারপর sort() ফাংশন ব্যবহার করে ভেক্টর ডিফ সাজান।
-
এখন 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
