I have $3$ boxes - $B_1, B_2, B_3$. Each box initially contains a mixture of $3$ different kind of fruits say - Apple, Orange, Mango. Our goal is to arrange the fruits in the boxes in such a manner that each box contains only one type of fruit. So you need to shift fruits from one box to another in order to make the arrangement. How to do this with minimum number of movements?

Say $9$ integers are given. As each box initially contains all $3$ types of fruits, you can divide $9$ integers into $3$ groups, each group representing the initial permutation of fruits in $B_1, B_2, B_3$ respectively. Consider: $10, 17, 20, 32, 29, 19, 43, 27, 28$. Fruits are represented in order of Apple, Orange & Mango. So The first box contains $10$ Apple, $17$ Orange & $20$ Mango and so on.

What is the minimum number of movements required so that the mentioned boxes contain only one type of fruit. Any box can contain any $1$ type of fruit.

  • $\begingroup$ To clarify: what is a "movement"? Do you allow only transpositions? (eg, an Apple from Box 1 is switched with a Mango from box 2)? $\endgroup$ – lulu Aug 12 '15 at 12:04
  • $\begingroup$ Movement means you can shift any fruit from one box to another. In the end, each box should contain any one type of fruits. $\endgroup$ – coderx Aug 12 '15 at 12:16
  • $\begingroup$ Have you tried anything? If I have understood you, there are only 6 possible solutions at least if you ignore pointless moves (eg Apple from #1->2 followed by Apple from #2->#1). Worst case you could just compare all 6, though surely you could say something about characterizing the best of them. $\endgroup$ – lulu Aug 12 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.