There are N chairs placed in circular order, some of them are occupied by a child while the rest are empty, you want to change the places of children so that they all sit next to each other, in one move you can tell a child to go in clockwise or anti-clockwise order until he reaches first empty chair and sit on it. Find the minimum number of moves required to achieve the goal.
In each move one of two things will happen:
1- if the chosen child was on the boundary of a block of occupied chairs and he is told to move in the direction of this block:
then length of one block of empty chairs will increase by 1 and length of another block will decrease by 1 (if it became 0 length the block disappears).
2- if the chosen child was in the middle of a block of occupied chairs or he was on the boundary but he is told to move away from direction of this block:
then length of one block of empty chairs will decrease by 1 (if it became 0 length the block disappears) and new block with 1 empty chair will appear.
Let S be total number of empty chairs among all N chairs, the given goal (all children forming a consecutive segment) is equivalent to the following condition: all empty chairs form a consecutive segment. So let’s say we want to get only one block of empty chairs of length exactly S and since in one move one block of empty chairs will increase by at most 1 then the answer is at least S-A where A is length of longest block of empty chairs.
we can show that the answer is exactly S-A if we show that we can always choose a move such that we can increase length of any block we want, choose the block of empty chairs that you want to increase its length, it must be surrounded by two occupied chairs, pick anyone of them and tell him to go the direction away from this block.
so the solution is just to count total number of empty chairs and calculate the sizes of each block and subtract the maximum length of empty chairs block from total number of empty chairs
Time complexity: O(N)