正確にk個のサブ配列を削除して配列のサイズを最大化し、C++で配列を素数にします

与えられたタスクは、配列内の残りのすべての要素が素数であり、残りの配列のサイズが最大になるように、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}です。

以下のプログラムで使用されるアプローチは次のとおりです

• まず、sieve（）関数を呼び出して、エラトステネスのふるいを使用して、すべての素数を別の配列prime[]に格納します

• 関数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