12. Integer to Roman

Roman numerals are greedy by nature: at every step you want the largest symbol that still fits. The move that removes all the special cases is to put the subtractive forms — 900 = CM, 400 = CD, 90 =…