Minimize cost to convert all array elements to 0 | Python3 program for the above approach ; Function to calculate the minimum cost of converting all array elements to 0 s ; Stores subarrays of 0 s only ; Traverse the array ; If consecutive 0 s occur ; Increment if needed ; Push the current length of consecutive 0 s in a vector ; Update lengths as 0 ; Sorting vector ; Stores the number of subarrays consisting of 1 s ; Traverse the array ; If current element is 1 ; Otherwise ; Increment count of consecutive ones ; Stores the minimum cost ; Traverse the array ; First element ; Traverse the subarray sizes ; Update cost ; Cost of performing X and Y operations ; Find the minimum cost ; Print the minimum cost ; Driver Code ; Function Call
import sys NEW_LINE def minimumCost ( binary , n , a , b ) : NEW_LINE INDENT groupOfZeros = [ ] NEW_LINE length = 0 NEW_LINE i = 0 NEW_LINE increment_need = True NEW_LINE while ( i < n ) : NEW_LINE INDENT increment_need = True NEW_LINE while ( i < n and binary [ i ] == 0 ) : NEW_LINE INDENT length += 1 NEW_LINE i += 1 NEW_LINE increment_need = False NEW_LINE DEDENT if ( increment_need == True ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT if ( length != 0 ) : NEW_LINE INDENT groupOfZeros . append ( length ) NEW_LINE DEDENT length = 0 NEW_LINE DEDENT groupOfZeros . sort ( ) NEW_LINE i = 0 NEW_LINE found_ones = False NEW_LINE NumOfOnes = 0 NEW_LINE while ( i < n ) : NEW_LINE INDENT found_ones = False NEW_LINE while ( i < n and binary [ i ] == 1 ) : NEW_LINE INDENT i += 1 NEW_LINE found_ones = True NEW_LINE DEDENT if ( found_ones == False ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT NumOfOnes += 1 NEW_LINE DEDENT DEDENT ans = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT curr = 0 NEW_LINE totalOnes = NumOfOnes NEW_LINE if ( i == 0 ) : NEW_LINE INDENT curr = totalOnes * a NEW_LINE DEDENT else : NEW_LINE INDENT mark = i NEW_LINE num_of_changes = 0 NEW_LINE for x in groupOfZeros : NEW_LINE INDENT if ( mark >= x ) : NEW_LINE INDENT totalOnes -= 1 NEW_LINE mark -= x NEW_LINE num_of_changes += x NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT curr = ( ( num_of_changes * b ) + ( totalOnes * a ) ) NEW_LINE DEDENT ans = min ( ans , curr ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 , 1 , 0 , 1 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE X = 10 NEW_LINE Y = 4 NEW_LINE minimumCost ( arr , N , X , Y ) NEW_LINE DEDENT