We can move 0's one by one to the right.
Let us see this with a partial example for 9 member array (4 0's and 4 1's)
0000_1111
00001_111 (move left)
000_10111 (Jump right)
000101_11 (3 left moves combined)
0001_1011 (Jump right)
0001101_1 (3 left moves combined)
00011_101 (Jump right)
00011101_ (3 left moves combined)
000111_10 (Jump right)
0001_1110 (2 right movs)
Here the first 0 reached the place! Now start with second zero!
Now what is the lower bound for number of moves?
It is obvious that all the zeros should jump across all the ones atleast once (Even the one's can jump the 0's. But both cases can be considered similar)!
So optimization is possible only with "moves" and not with "Jumps"
It means If we can perform maximum number of Jumps with a single move then it will be the optimum solution!
But "Maximum jumps without move" is possible only with one combination - The alternating combination...
(For 9 digit array, it is..)
_01010101 (We can perform 4 jumps here)
10101010_ (After 4 jumps)
So, I have decided to proceed from here! Let me see whether I can bring all 0's to the left with "minimum moves"
1_1010100 (Three jumps- The maximum possible after
11_010100 (Move left)
111010_00 (2 Jumps - Maximum possible after discarding)
11101_000 (Move right)
111_10000 (1 Jump)
1111_0000 (Hurray... We got it!)
But... How to reach the "alternating" combination???
Easy!
If you notice carefully we have already done it!
Just use the "Reverse Mirror" of this...
It is as follows,
0000_1111
00001_111 (Move left)
000_10111 (1 Jump)
00_010111 (Move right)
001010_11 (2 Jumps)
0010101_1 (Move left)
0_1010101 (3 Jumps)
_01010101 (Move right)
