Блог пользователя AjaySabarish

Автор AjaySabarish, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it`s 1391D - 505 if n = 2

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.