redcoder23's blog

Equalize the array
By redcoder23, history, 4 years ago, In English

You have N candies distributed unevenly in N containers. You can move one candy from a container to an adjacent container. You have to make moves such that finally each container has one candy. What is the strategy that minimizes the number of moves to keep the time complexity O(N)?

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the problem source?

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

    It was asked in a recent online test of uber.

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

      You can solve this greedily. The first cup should get the leftmost candy. The second cup should get the second leftmost candy. Etc.

      You can implement this with two pointers. One pointer to current cup and other pointer to next candy. Cup pointer always moves from one cup to the next adjacent cup. Candy pointer going from a candy to the next candy (which may be in the same cup or some later cup, not necessarily the next one).

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

It is greedy. Put the indexes of the empty containers into a list. Walk from left to right through the list of candies which have to be moved. Move them to the next (lowest) container without a candy. Sum up the distances of moved candies.

Edit, proof: I am not sure how to do that. An optimal pairing of candy/container is so that there is no "overlap" of pairs. Let $$$ca_i$$$ be candys and $$$co_j$$$ be containers. Then there must not be two pairings with $$$(ca_{i1}, co_{j1}),(ca_{i2}, co_{j2})$$$ with $$$co_{j1}>ca_{i1}$$$ and $$$co_{j2}<ca_{i2}$$$ while $$$ca_{i1}<ca_{i2}$$$ .

Or more understandable, the movings of candies of different direction must not intersect. Because it they would, we can change two of them to get a better result.

So, how to proof that the above greedy does create a pairing without intersections?

→ Reply