Minimum toggles to partition a binary array so that it has first 0 s then 1 s | Function to calculate minimum toggling required by using Dynamic programming ; Fill entries in zero [ ] such that zero [ i ] stores count of zeroes to the left of i ( exl ; If zero found update zero [ ] array ; Finding the minimum toggle required from every index ( 0 to n - 1 ) ; Driver Program
def minToggle ( arr , n ) : NEW_LINE INDENT zero = [ 0 for i in range ( n + 1 + 1 ) ] NEW_LINE zero [ 0 ] = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( arr [ i - 1 ] == 0 ) : NEW_LINE INDENT zero [ i ] = zero [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT zero [ i ] = zero [ i - 1 ] NEW_LINE DEDENT DEDENT ans = n NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = min ( ans , i - zero [ i ] + zero [ n ] - zero [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 1 , 0 , 1 , 1 , 0 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minToggle ( arr , n ) ) NEW_LINE