12. Integer to Roman

List every Roman value (including the subtractive forms like 900=CM and 4=IV) from largest to smallest. Repeatedly append the largest symbol that still fits and subtract its value, until the number reaches zero.

Idea

Roman numerals are written largest-to-smallest. If we include the six subtractive forms (CM, CD, XC, XL, IX, IV) directly in our value table, the whole conversion becomes a clean greedy loop: always take the biggest symbol that doesn't overshoot.

Algorithm

1. Build a descending list of (value, symbol) pairs including the subtractive forms.
2. For each pair, while num >= value, append symbol and subtract value.
3. Return the accumulated string.

Worked example: 1994

Result: "MCMXCIV".

Complexity

• Time: O(1) — at most a constant number of symbols (num ≤ 3999).
• Space: O(1).

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }
        return sb.toString();
    }
}