AjaySabarish's blog

An Interesting Problem
By AjaySabarish, history, 4 years 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

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it`s 1391D - 505 if n = 2

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply