Maximize the size of array by deleting exactly k sub | C ++ implementation of the approach ; Sieve of Eratosthenes ; Function to return the size of the maximized array ; Insert the indices of composite numbers ; Compute the number of prime between two consecutive composite ; Sort the diff vector ; Compute the prefix sum of diff vector ; Impossible case ; Delete sub - arrays of length 1 ; Find the number of primes to be deleted when deleting the sub - arrays ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e7 + 5 ; bool prime [ N ] ; void seive ( ) { for ( int i = 2 ; i < N ; i ++ ) { if ( ! prime [ i ] ) { for ( int j = i + i ; j < N ; j += i ) { prime [ j ] = 1 ; } } } prime [ 1 ] = 1 ; } int maxSizeArr ( int * arr , int n , int k ) { vector < int > v , diff ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ arr [ i ] ] ) v . push_back ( i ) ; } for ( int i = 1 ; i < v . size ( ) ; i ++ ) { diff . push_back ( v [ i ] - v [ i - 1 ] - 1 ) ; } sort ( diff . begin ( ) , diff . end ( ) ) ; for ( int i = 1 ; i < diff . size ( ) ; i ++ ) { diff [ i ] += diff [ i - 1 ] ; } if ( k > n || ( k == 0 && v . size ( ) ) ) { return -1 ; } else if ( v . size ( ) <= k ) { return ( n - k ) ; } else if ( v . size ( ) > k ) { int tt = v . size ( ) - k ; int sum = 0 ; sum += diff [ tt - 1 ] ; int res = n - ( v . size ( ) + sum ) ; return res ; } } int main ( ) { seive ( ) ; int arr [ ] = { 2 , 4 , 2 , 2 , 4 , 2 , 4 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 2 ; cout << maxSizeArr ( arr , n , k ) ; return 0 ; }