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?
Any specific reason for downvoting or it's just bored kids?
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.
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.
Whoops I completely misread that part. That's what I get for skimming.
it`s 1391D - 505 if n = 2
Order of flips doesn`t matter so dp(i, j)- minimum number of steps to make first i-1 elements equal to 0 and i-th element to j.
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?
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.
Sorry got confused,thanks but how would the transitions look like?