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 int num = 0 ; ; Compute the number of prime between two consecutive composite num = 0 ; ; 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
using System ; using System . Collections . Generic ; class GFG { static int N = 1000005 ; static int [ ] prime = new int [ N ] ; static void seive ( ) { for ( int i = 2 ; i < N ; i ++ ) { if ( prime [ i ] == 0 ) { for ( int j = i + i ; j < N ; j += i ) { prime [ j ] = 1 ; } } } prime [ 1 ] = 1 ; } static int maxSizeArr ( int [ ] arr , int n , int k ) { List < int > v = new List < int > ( ) ; List < int > diff = new List < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ arr [ i ] ] == 1 ) { v . Add ( i ) ; } } for ( int i = 1 ; i < v . Count ; i ++ ) { diff . Add ( v [ i ] - v [ i - 1 ] - 1 ) ; } diff . Sort ( ) ; for ( int i = 1 ; i < diff . Count ; i ++ ) { diff [ i ] = diff [ i ] + diff [ i - 1 ] ; } if ( k > n || ( k == 0 && v . Count > 0 ) ) { return - 1 ; } else if ( v . Count <= k ) { return ( n - k ) ; } else if ( v . Count > k ) { int tt = v . Count - k ; int sum = 0 ; sum += diff [ tt - 1 ] ; int res = n - ( v . Count + sum ) ; return res ; } return 1 ; } public static void Main ( String [ ] args ) { seive ( ) ; int [ ] arr = { 2 , 4 , 2 , 2 , 4 , 2 , 4 , 2 } ; int n = arr . Length ; int k = 2 ; Console . WriteLine ( maxSizeArr ( arr , n , k ) ) ; } }