codingkshatriya's blog

By codingkshatriya, history, 6 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Any specific reason for downvoting or it's just bored kids?

»
6 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Whoops I completely misread that part. That's what I get for skimming.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it`s 1391D - 505 if n = 2

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry got confused,thanks but how would the transitions look like?