Maximize the size of array by deleting exactly k sub | Python implementation of above 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
N = 10000005 NEW_LINE prime = [ False ] * N NEW_LINE def seive ( ) : NEW_LINE INDENT for i in range ( 2 , N ) : NEW_LINE INDENT if not prime [ i ] : NEW_LINE INDENT for j in range ( i + 1 , N ) : NEW_LINE INDENT prime [ j ] = True NEW_LINE DEDENT DEDENT DEDENT prime [ 1 ] = True NEW_LINE DEDENT def maxSizeArr ( arr , n , k ) : NEW_LINE INDENT v , diff = [ ] , [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if prime [ arr [ i ] ] : NEW_LINE INDENT v . append ( i ) NEW_LINE DEDENT DEDENT for i in range ( 1 , len ( v ) ) : NEW_LINE INDENT diff . append ( v [ i ] - v [ i - 1 ] - 1 ) NEW_LINE DEDENT diff . sort ( ) NEW_LINE for i in range ( 1 , len ( diff ) ) : NEW_LINE INDENT diff [ i ] += diff [ i - 1 ] NEW_LINE DEDENT if k > n or ( k == 0 and len ( v ) ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT elif len ( v ) <= k : NEW_LINE INDENT return ( n - k ) NEW_LINE DEDENT elif len ( v ) > k : NEW_LINE INDENT tt = len ( v ) - k NEW_LINE s = 0 NEW_LINE s += diff [ tt - 1 ] NEW_LINE res = n - ( len ( v ) + s ) NEW_LINE return res NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT seive ( ) NEW_LINE arr = [ 2 , 4 , 2 , 2 , 4 , 2 , 4 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE print ( maxSizeArr ( arr , n , k ) ) NEW_LINE DEDENT