Integer to Roman

medium string greedy

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Inputnum = 1994

Output"MCMXCIV"

1000 → M, 900 → CM, 90 → XC, 4 → IV.

num (1..3999)

def int_to_roman(num):
    pairs = [(1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),(50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I")]
    out = ""
    for v, sym in pairs:
        while num >= v:
            out += sym
            num -= v
    return out

function intToRoman(num) {
  const pairs = [[1000,"M"],[900,"CM"],[500,"D"],[400,"CD"],[100,"C"],[90,"XC"],[50,"L"],[40,"XL"],[10,"X"],[9,"IX"],[5,"V"],[4,"IV"],[1,"I"]];
  let out = "";
  for (const [v, sym] of pairs) {
    while (num >= v) { out += sym; num -= v; }
  }
  return out;
}

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

string intToRoman(int num) {
    vector<pair<int, string>> pairs = {{1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},{100,"C"},{90,"XC"},{50,"L"},{40,"XL"},{10,"X"},{9,"IX"},{5,"V"},{4,"IV"},{1,"I"}};
    string out;
    for (auto& p : pairs) {
        while (num >= p.first) { out += p.second; num -= p.first; }
    }
    return out;
}

Explanation

To turn a number into a Roman numeral, we greedily peel off the largest chunk we can at every step. We keep a list of value-symbol pairs sorted from biggest to smallest, including the special subtractive ones like 900 → "CM" and 4 → "IV".

For each pair (v, sym), while num is still at least v, we append sym to the answer and subtract v from num. Then we move to the next smaller pair and repeat until num reaches 0.

Always taking the largest possible value first guarantees the shortest, correct numeral, because Roman numerals are built by writing the highest denominations on the left.

Example: num = 1994. We peel 1000 → M (left with 994), then 900 → CM (94), then 90 → XC (4), then 4 → IV (0), giving "MCMXCIV".

Since the input is capped at 3999, the loop does a bounded amount of work, so it effectively runs in constant time.

Time: O(1) (≤ 3999 bounded) Space: O(1)