Initialize prefix arrays to store number of changes required to put 1 s at either even or odd position
oddone = [ 0 ] * ( n + 1 ) NEW_LINE evenone = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE