LeetCode. 12.Integer to Roman

[Link] https://leetcode.com/problems/integer-to-roman/

Greedy denomination selection

Roman numerals use descending place-value symbols, with six subtractive forms: IV and IX represent 4 and 9, XL and XC represent 40 and 90, and CD and CM represent 400 and 900. At each step, take the largest denomination no greater than the remaining value, append its symbol, and subtract that denomination. Repeat until nothing remains. The table includes the subtractive forms as single denominations, so the greedy choices directly produce the standard notation.

This representation is canonical for the problem’s range, 1 through 3999. For values below 4000, the thousands digit is represented by zero to three Ms. Each remaining decimal digit is independent: hundreds use C, D, CD, CM; tens use X, L, XL, XC; and ones use I, V, IV, IX. For any such digit, greedily choosing its largest applicable form yields exactly its conventional single Roman digit representation. Since the place values do not overlap and each digit has a unique such form, concatenating them from largest to smallest gives the unique canonical numeral. The descending table performs precisely this decomposition.

Java

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 result = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(symbols[i]);
                num -= values[i];
            }
        }
        return result.toString();
    }
}

Let $L$ be the output length. The loop appends each output symbol once, so the time complexity is $O(L)$ and the result storage is $O(L)$. Under the problem constraint $1 \le num \le 3999$, the output length is bounded by a constant.