-1

Given an array of 1 and 0. We need to move all 1's to 0 with minimum cost

  1. We can move either left or right , multiple one's cannot be moved to same position.

  2. Each movement cost is 1.

Ex:

    array = 0001101
    
    Here the optimal solution is 5 , x means it cannot be occupied 
    1. 3rd index to 2nd index -> cost = 1 , array = 00xx101  
    2. 4th index to 1st index -> cost = 3 , array = 0xxxx01
    3. 6th index to 5th index -> cost = 1 , array = 0xxxxxx

I tried it by bruteforce way of finding it's nearest 0 and moving it , but with no success. Need some expertise help here.

Edit:

I solved this problem using recusrion and memoization. Quite similar question with solution here - https://leetcode.com/problems/minimum-total-distance-traveled/solutions/2816471/recursion-memoization/

Roshan
  • 2,144
  • 2
  • 16
  • 28
  • 1
    Please share more details, like the code involved – Nico Haase Aug 15 '22 at 12:33
  • Does this answer your question? [What is the minimum number of adjacent swaps needed to segregate a list of 0s and 1s?](https://stackoverflow.com/questions/63513603/what-is-the-minimum-number-of-adjacent-swaps-needed-to-segregate-a-list-of-0s-an) – Dave Aug 15 '22 at 13:56
  • @Dave I think the OP's problem is not equivalent to the problem you pointed. The OP wants to get rid of the ones (by moving them to zero positions). He doesn't want to gather ones and zeros together. Also, it seems the OP has the additional constraint that the zeroes a one pass by during his way (and the one's original position) can not be used in future moves of other ones. – joaopfg Aug 15 '22 at 14:03
  • @JohnDoe Agreed; my mistake. – Dave Aug 15 '22 at 14:18

1 Answers1

0

This can be solved with dynamic programming.

Let the state space be the set of strings with n characters from the alphabet {0, 1, x}.

The transitions are defined by changing ones and zeros to x after moving a 1 to the closest 0 to the left or to the right.

The base cases are the strings full of 0 and x characters (for which you return zero) or a string from which you cannot move (for which you return -1).

For example, if the initial state is 0001101, the possible transitions are 00xx101, 0001xx1 and 00011xx.

The solution for a state is the minimum of the solutions for all the possible transitions (plus the cost of doing the transition) only for the solutions that are not -1. If all the transition solutions are -1, the solution for the state is also -1.

To store solutions for states, you can use a hash map.

joaopfg
  • 1,227
  • 2
  • 9
  • 18
  • What you’re describing here seems more like a BFS over the space than dynamic programming. It seems like the search space might be pretty big. Do you have any bounds on how quickly this will run? – templatetypedef Aug 15 '22 at 13:41
  • What I described is a top down dynamic programming approach that takes profit of the overlaps between sub problems. I'm also making the greedy observation that the only interesting transitions are defined by changing ones and zeros to x after moving a 1 to the closest 0 to the left or to the right. This reduces the search space a lot. I'm trying to estimate the time complexity. I think it depends on how optimized we do the transitions – joaopfg Aug 15 '22 at 13:46
  • Thanks for the answer @JohnDoe. I took quite same approach https://leetcode.com/problems/minimum-total-distance-traveled/solutions/2816471/recursion-memoization/ – Roshan Mar 11 '23 at 15:56