GATE 2026 IN – Question 5
A coin with heads facing up is denoted by H, and a coin with tails facing up is denoted by T. Six coins have the starting arrangement H H H T T T and the final arrangement T T T H H H.
A “step” is defined as interchanging a pair of adjacent coins without flipping them. The minimum number of steps needed to go from the starting arrangement to the final arrangement is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 9
Explanation
Each of the three T coins must move past each of the three H coins. There are therefore $3 \times 3=9$ H–T pairs whose relative order must reverse.
One adjacent interchange can reverse the order of only one such pair, so at least nine steps are necessary. Moving the T coins leftwards successively uses three swaps per T coin and achieves the final arrangement in nine steps.
The minimum is **9 steps (C)**.