Integer to Roman

Problem

Convert an integer to a Roman numeral string.

Input:  num = 1994
Output: "MCMXCIV"

Python Solution

def int_to_roman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    result = []
    for value, symbol in zip(values, symbols):
        while num >= value:
            result.append(symbol)
            num -= value
    return "".join(result)

C++ Solution

string intToRoman(int num) {
    vector<int> values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    vector<string> symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    string result;
    for (int i = 0; i < values.size(); i++) {
        while (num >= values[i]) {
            result += symbols[i];
            num -= values[i];
        }
    }
    return result;
}

Java Solution

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();
    }
}

Complexity

Time: O(1) — the value list has a fixed length of 13 entries, and the total number of symbols appended is bounded regardless of input size (at most 3999). Space: O(1) — fixed-size lookup tables.