Maximize the size of array by deleting exactly k sub | Javascript 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
const N = 1e7 + 5 ; let prime = new Array ( N ) ; function seive ( ) { for ( let i = 2 ; i < N ; i ++ ) { if ( ! prime [ i ] ) { for ( let j = i + i ; j < N ; j += i ) { prime [ j ] = 1 ; } } } prime [ 1 ] = 1 ; } function maxSizeArr ( arr , n , k ) { let v = new Array ( ) ; let diff = new Array ( ) ; for ( let i = 0 ; i < n ; i ++ ) { if ( prime [ arr [ i ] ] ) v . push ( i ) ; } for ( let i = 1 ; i < v . length ; i ++ ) { diff . push ( v [ i ] - v [ i - 1 ] - 1 ) ; } diff . sort ( ( a , b ) => a - b ) ; for ( let i = 1 ; i < diff . length ; i ++ ) { diff [ i ] += diff [ i - 1 ] ; } if ( k > n || ( k == 0 && v . length ) ) { return - 1 ; } else if ( v . length <= k ) { return ( n - k ) ; } else if ( v . length > k ) { let tt = v . length - k ; let sum = 0 ; sum += diff [ tt - 1 ] ; let res = n - ( v . length + sum ) ; return res ; } } seive ( ) ; let arr = [ 2 , 4 , 2 , 2 , 4 , 2 , 4 , 2 ] ; let n = arr . length ; let k = 2 ; document . write ( maxSizeArr ( arr , n , k ) ) ;