Boys and Girls – SPOJ problem

This problem is from SPOJ. Please follow this link if you want to try on your own!

The problem is as follows.

Given some number of boys and girls, we have to arrange them in a row such that the same gender appear together is minimized.
We have to find the minimum number of any gender appear together in any arrangement.

For example

Given that there are 3 boys and 3 girls, we can arrange them alternatively B G B G B G. So the minimum number is 1
If there are 4 boys and 1 girl, we can arrange them like B B G B B, so the minimum number is 2.

Solution approach:

The solution is very simple. We have to divide the bigger number by smaller number plus 1. 
Consider that there are N boys and M girls (N > M). The optimal way of arranging them is to put one girl between a group of (N/M+1) boys.

Here is the C++ code.

Leave a Reply

Your email address will not be published. Required fields are marked *