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
< ? php function minToggle ( $ arr , $ n ) { $ zero [ 0 ] = 0 ; $ zero [ $ n + 1 ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; ++ $ i ) { if ( $ arr [ $ i - 1 ] == 0 ) $ zero [ $ i ] = $ zero [ $ i - 1 ] + 1 ; else $ zero [ $ i ] = $ zero [ $ i - 1 ] ; } $ ans = $ n ; for ( $ i = 1 ; $ i <= $ n ; ++ $ i ) $ ans = min ( $ ans , $ i - $ zero [ $ i ] + $ zero [ $ n ] - $ zero [ $ i ] ) ; return $ ans ; } $ arr = array ( 1 , 0 , 1 , 1 , 0 ) ; $ n = sizeof ( $ arr ) ; echo minToggle ( $ arr , $ n ) , " STRNEWLINE " ; ? >