A word-and-number arrangement machine, when given an input line of words and numbers, rearranges it in steps. In each step two shifts happen together: the smallest odd number not already shifted is taken out and placed at the extreme left end of the line, and at the same time the largest even number not already shifted is taken out and placed at the extreme right end. If only one of the two kinds is still left, that step makes only that one shift. Every other element keeps its relative position, and the machine stops once every number has been shifted. Input: candle 75 ember 42 grove 19 hazel 68 iris 53. How many steps are needed to complete the rearrangement of the above input?

Question

Accepted Answer

3. Odd numbers: 75, 19, 53. Even numbers: 42, 68. Step 1: 19 candle 75 ember 42 grove hazel iris 53 68. Step 2: 53 19 candle 75 ember grove hazel iris 68 42. The even numbers are now exhausted, but 75 is still unshifted, so Step 3 makes the odd shift alone: 75 53 19 candle ember grove hazel iris 68 42. Three steps in all. Stopping when the evens run out gives two; counting one step per number gives five, which would be right only if the two shifts never happened together.

Step-by-Step Solution

Master this topic in 30 minutes a day.

More Input-Output practice