A word-and-number arrangement machine, when given an input line of words and numbers, rearranges it in steps. In each step the largest number that has not already been shifted is taken out of the line and put back immediately to the left of whichever word then stands furthest to the left. The rest of the line is left exactly as it stands, and the machine finishes when no unshifted number is left. Input: 29 lotus 74 mint 56 nectar 38 olive. At which step of the above arrangement does the line "29 74 56 38 lotus mint nectar olive" appear?

Question

Accepted Answer

Step 3. Lotus is the leftmost word at every stage. Step 1: 29 74 lotus mint 56 nectar 38 olive. Step 2: 29 74 56 lotus mint nectar 38 olive. Step 3: 29 74 56 38 lotus mint nectar olive — the line asked about. Step 4, the last, would be 74 56 38 29 lotus mint nectar olive, with 29 finally lifted from the head and tucked in beside lotus. The giveaway is that 29 is still sitting at the very front here: it is the smallest number and so the last to be shifted, which means one move remains.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice