C++-এ সঠিক Kটি সাবঅ্যারে ডিলিট করে অ্যারেকে প্রাইম করে সর্বোচ্চ আকার পাওয়া

দেওয়া কাজ হল একটি দেওয়া অ্যারে Arr[] থেকে সঠিক Kটি সাবঅ্যারে ডিলিট করা যাতে অ্যারের বাকি সকল উপাদান প্রাইম হয় এবং বাকি অ্যারের আকার সর্বোচ্চ হয়।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট

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

আউটপুট

ব্যাখ্যা - K=2, অর্থাৎ শুধু ২টি সাবঅ্যারে ডিলিট করতে হবে। ডিলিট করা সাবঅ্যারেগুলো হল Arr[0] এবং Arr[3…5] যা বাকি অ্যারে Arr[]={3,3,3} রেখে দেয় যেখানে সব উপাদান প্রাইম এবং আকার সর্বোচ্চ।

ইনপুট

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

আউটপুট

ব্যাখ্যা - ডিলিট করা সাবঅ্যারেগুলো হল Arr[1] এবং Arr[4…6] এবং বাকি প্রাইম অ্যারে হল Arr[]={7,2,11}।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

প্রথমে সিভ অফ এরাটোস্থেনিস ব্যবহার করে সকল প্রাইম নম্বর prime[] অ্যারেতে সংরক্ষণ করুন sieve() ফাংশন কল করে।
MaxSize() ফাংশনে i=0 থেকে i<N পর্যন্ত লুপ চালান এবং কমপোজিট সংখ্যাগুলোর ইনডেক্স নম্বর একটি ভেক্টর vect-এ সংরক্ষণ করুন।
এরপর i=1 থেকে i<vect.size() পর্যন্ত লুপ চালান দুটি কনsekutিভ কমপোজিটের মাঝপথে কতগুলো প্রাইম আছে তা বের করে diff ভেক্টরে সংরক্ষণ করুন।
diff ভেক্টরটি sort() ফাংশন দিয়ে সর্ট করুন।
আরেক লুপ i=1 থেকে i<diff.size() চালান diff ভেক্টরের প্রিফিক্স সাম বের করতে যা আমাদের জানাবে কতগুলো প্রাইম ডিলিট করতে হবে।
একটি if স্টেটমেন্ট দিয়ে імপসিবল কেস চেক করুন, অর্থাৎ যখন K=0 এবং কোনো কমপোজিট নেই।
যদি K কমপোজিটের সংখ্যার চেয়ে বড় বা সমান হয়, তবে সব কমপোজিটসহ এক্সট্রা প্রাইম ডিলিট করুন এবং ডিলিট করা সাবঅ্যারের আকার ১ রাখুন অপ্টিমাল আউটপুট পেতে।
যদি 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);
    }
    /*দুটি কনsekutিভ কমপোজিটের মাঝপথে প্রাইম সংখ্যার গণনা*/
    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;
    }
    // লেথ ১-এর সাবঅ্যারে ডিলিট
    else if (vect.size() <= K){
        return (N - 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;
}