#12
Integer to Roman
Medium Greedy table
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Convert an integer from 1 to 3999 into a Roman numeral.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: write a number in Roman numerals.
Why this works: include the subtractive pairs (CM, XC, IV…) in the value table, then greedily take the biggest piece that fits.
Example: 58
50 → L, 8 left5 → V, 3 leftIII → "LVIII"
✦Hints open one at a time
Put the subtractive forms (CM, CD, XC, XL, IX, IV) into the value table too.
Greedily take the largest value that still fits.
↗Approach
Arrays of 13 values and symbols in descending order. For each, while num >= value, append the symbol and subtract.
</>Solution (Java)
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 sb = new StringBuilder();
for (int i = 0; i < vals.length; i++) {
while (num >= vals[i]) { // take the biggest piece that fits
sb.append(syms[i]);
num -= vals[i];
}
}
return sb.toString();
}
}!Common mistake
Leaving out the subtractive pairs, which produces IIII instead of IV.
Complexity
- Time: O(1) — the output is at most 15 characters.
- Space: O(1).
Topic: Strings
🎬 Episodes 16–20: video coming soon