Integer to Roman

Medium
160.

Integer to Roman

Integer to Roman is a medium coding problem on strings, hash table and math, asked in Amazon, Microsoft, Adobe and Twitter interviews.

Given an integer num between 1 and 3999, convert it to a roman numeral.

Symbols are written largest to smallest and added up, except for the six subtractive pairs IV (4), IX (9), XL (40), XC (90), CD (400) and CM (900).

Example 1

Input
num = 3
Output
III

Example 2

Input
num = 58
Output
LVIII
Explanation
50 + 5 + 3.

Example 3

Input
num = 1994
Output
MCMXCIV
Explanation
1000 + 900 + 90 + 4.

Constraints

  • 1 <= num <= 3999
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Integer to Roman — Solution in Python, Java & C++

Integer to Roman solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Integer to Roman is a medium coding problem on strings, hash table and math, asked in Amazon, Microsoft, Adobe and Twitter interviews.

Problem statement

Given an integer num between 1 and 3999, convert it to a roman numeral.

Symbols are written largest to smallest and added up, except for the six subtractive pairs IV (4), IX (9), XL (40), XC (90), CD (400) and CM (900).

Example 1

Input: num = 3
Output: III

Example 2

Input: num = 58
Output: LVIII
Explanation: 50 + 5 + 3.

Example 3

Input: num = 1994
Output: MCMXCIV
Explanation: 1000 + 900 + 90 + 4.

Constraints

  • 1 <= num <= 3999

Hints for Integer to Roman

  1. Hint 1

    Put the six subtractive pairs into the value table alongside the seven plain symbols — thirteen values in all.

  2. Hint 2

    Walk the table from the largest value down, appending the symbol and subtracting while the value still fits.

  3. Hint 3

    Greedy is exact here because each table entry is a distinct denomination that only one representation can use.

How to solve Integer to Roman

Treat the seven symbols plus the six subtractive pairs as thirteen denominations and pay out the number greedily from the largest denomination down.

Approach

  1. List values [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] with their symbols.
  2. For each value in order, while num >= value, append the symbol and subtract the value.
  3. Join the pieces.

Why it works

Each denomination is at least twice the next smaller one except the subtractive pairs, which are unique ways to express their value; roman numerals are defined so that the canonical representation is the one greedy produces. Since a symbol never repeats beyond what greedy emits (at most three Xs, one V, etc.), the result is the standard form.

Complexity

  • Time — O(1) — at most 15 symbols
  • Space — O(1)

Pitfalls

  • Leaving out the subtractive pairs makes greedy emit VIIII for 9.
  • The table must be in descending order for greedy to be correct.

Reference solution

Python

def intToRoman(num: int) -> str:
    vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    out = []
    for v, sym in zip(vals, syms):
        while num >= v:
            out.append(sym)
            num -= v
    return "".join(out)

Java

public static 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 sb = new StringBuilder();
    for (int i = 0; i < vals.length; i++) {
        while (num >= vals[i]) {
            sb.append(syms[i]);
            num -= vals[i];
        }
    }
    return sb.toString();
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets