Integer to Roman Numeral

medium string greedy

Problem

Convert an integer between 1 and 3999 into its Roman numeral string. Roman numerals are formed greedily: list every value-symbol pair from largest to smallest — including the six subtractive ones (CM, CD, XC, XL, IX, IV) — and at each step append the largest pair whose value is at most the remaining number, then subtract.

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

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