A word-and-number arrangement machine, when given an input line of words and numbers, rearranges it in steps. Reading only the numbers, from left to right, the machine finds the leftmost pair of neighbouring numbers standing out of ascending order and makes those two numbers trade the places they stand in. Words never move at all, and the machine stops as soon as the numbers of the line read in ascending order from left to right. Input: 58 tabla 34 sitar 71 veena 26. How many steps are needed to complete the rearrangement of the above input?

Question

Accepted Answer

4. The numbers read 58, 34, 71, 26. Step 1 swaps 58 and 34: 34 tabla 58 sitar 71 veena 26 (numbers 34, 58, 71, 26). Step 2 swaps 71 and 26: 34 tabla 58 sitar 26 veena 71. Step 3 swaps 58 and 26: 34 tabla 26 sitar 58 veena 71. Step 4 swaps 34 and 26: 26 tabla 34 sitar 58 veena 71, and the numbers now ascend, so the machine stops: 4 steps. "3" stops while 34 still stands before 26. "5" adds a needless step after the numbers already ascend. "6" counts every pair of numbers that had to change order rather than the swaps actually made.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice