### codingkshatriya's blog

By codingkshatriya, history, 6 weeks ago,

Given a binary array, convert all the elements to zero Array (array with only zeros) in minimum number of steps

In one step we can choose any 2 adjacent elements and flip them together, or you can choose the last or first element and flip that particular element alone.

Input : N ( 1 <= N <= 1e5) Array elements ( 0 <= a[i] <= 1)

Output : Minimum number of steps to convert the binary array to all zeros

Sample : [1,0,1] Anwer is 2 ( one possible way is choose the second and third elements, flip them and then choose the first and second elements and flip them)

Can anyone help me solve this?

• +13

 » 6 weeks ago, # |   -12 Any specific reason for downvoting or it's just bored kids?
 » 6 weeks ago, # | ← Rev. 2 →   -12 If there's an odd number of 1s in the original array then there is no solution, clearly.It seems like you can greedily make flips such that the leftmost 1 in the array is the left side of the flip. Do this until the array is all 0s. I could be wrong though, I didn't actually think about it that much lol. I'll leave it as an exercise to either prove or disprove the correctness of my algorithm. EDIT: This is wrong because I misread the portion involving the edges. This means a dp approach with a similar idea should suffice.
•  » » 6 weeks ago, # ^ |   0 Why is there no solution if the number of ones is odd? let us say array is 1 0 0 0 , we can just choose the first element and flip it.In one step we can choose any 2 adjacent elements and flip them together, or you can choose the last or first element and flip that particular element alone.
•  » » » 6 weeks ago, # ^ |   0 Whoops I completely misread that part. That's what I get for skimming.
 » 6 weeks ago, # |   0 its 1391D - 505 if n = 2
 » 6 weeks ago, # |   +19 Order of flips doesnt matter so dp(i, j)- minimum number of steps to make first i-1 elements equal to 0 and i-th element to j.
•  » » 6 weeks ago, # ^ |   0 How is the order irrelevant ? let us say array is 0 0 1 0 and the operations are (2,3) (1,2) (1), clearly if we change the order the result changes, can you please explain that?
•  » » » 6 weeks ago, # ^ |   +3 He's right. Think of each flip as adding a counter to the indices your flipping. If there is an odd number of counters on an index, that element changes. It doesn't matter the order in which you place the counters. At the end of the flips, each index will have the same amount of counters regardless of the order, if that makes sense.
•  » » » » 6 weeks ago, # ^ |   0 Sorry got confused,thanks but how would the transitions look like?