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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Math, Greedy
- Asked at: Amazon, Microsoft, Adobe, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
Put the six subtractive pairs into the value table alongside the seven plain symbols — thirteen values in all.
Hint 2
Walk the table from the largest value down, appending the symbol and subtracting while the value still fits.
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
- List values
[1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]with their symbols. - For each value in order, while
num >= value, append the symbol and subtract the value. - 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
VIIIIfor 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