Maximize the size of array by deleting exactly k sub | Java 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
import java . util . * ; class GFG { static int N = 10000005 ; 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 ) { ArrayList < Integer > v = new ArrayList < Integer > ( ) ; ArrayList < Integer > diff = new ArrayList < Integer > ( ) ; int num = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ arr [ i ] ] == 1 ) { v . add ( i ) ; } } num = 0 ; for ( int i = 1 ; i < v . size ( ) ; i ++ ) { diff . add ( v . get ( i ) - v . get ( i - 1 ) - 1 ) ; } Collections . sort ( diff ) ; for ( int i = 1 ; i < diff . size ( ) ; i ++ ) { diff . set ( i , diff . get ( i ) + diff . get ( i - 1 ) ) ; } if ( k > n || ( k == 0 && v . size ( ) > 0 ) ) { 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 . get ( tt - 1 ) ; int res = n - ( v . size ( ) + 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 ; System . out . println ( maxSizeArr ( arr , n , k ) ) ; } }