Integer to Roman
Integer to Roman is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (one lookup per decimal digit), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (greedy over 13 symbols) up.
Problem
Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. A number is normally written from the largest symbol to the smallest and the values are added, so 27 is XXVII.
Six values use a subtractive form instead, where a smaller symbol placed before a larger one is subtracted: 4 = IV, 9 = IX, 40 = XL, 90 = XC, 400 = CD, 900 = CM. No other subtractive pairs exist, and I, X, C, M may appear at most three times in a row.
Given an integer num, return its Roman numeral as a string.
Examples
Example 1
- Input
num = 2024- Output
"MMXXIV"- Why
- 2000 = MM, 20 = XX, 4 = IV.
Example 2
- Input
num = 49- Output
"XLIX"- Why
- 40 = XL and 9 = IX. Writing IL for 49 is not allowed.
Example 3
- Input
num = 3888- Output
"MMMDCCCLXXXVIII"- Why
- Every place uses the longest additive form: MMM, DCCC, LXXX, VIII.
Constraints
1 <= num <= 3999
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (greedy over 13 symbols) | O(1) | O(1) |
| Optimal (one lookup per decimal digit) | O(1) | O(1) |
1Brute force (greedy over 13 symbols)
O(1)num is at most 3999, so at most 15 symbols are appended over 13 table entries.O(1)Two fixed tables; the output has at most 15 characters.List the 13 values that have their own spelling, from 1000 (M) down to 1 (I), including the subtractive pairs like 900 (CM) and 4 (IV). Walk the list and, while the current value fits into what is left of num, append its symbol and subtract it.
- values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] with matching symbols.
- For each index i: while num >= values[i], append symbols[i] and num -= values[i].
- Return the built string.
class Solution {
public String intToRoman(int num) {
int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.length; i++) {
while (num >= values[i]) {
sb.append(symbols[i]);
num -= values[i];
}
}
return sb.toString();
}
}class Solution:
def intToRoman(self, num: int) -> str:
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
parts = []
for v, s in zip(values, symbols):
while num >= v:
parts.append(s)
num -= v
return "".join(parts)class Solution {
public:
string intToRoman(int num) {
int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string res;
for (int i = 0; i < 13; i++) {
while (num >= values[i]) {
res += symbols[i];
num -= values[i];
}
}
return res;
}
};function intToRoman(num) {
const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
let res = "";
for (let i = 0; i < values.length; i++) {
while (num >= values[i]) {
res += symbols[i];
num -= values[i];
}
}
return res;
}2Optimal (one lookup per decimal digit)
O(1)Exactly four table lookups and one concatenation.O(1)The four fixed tables hold 33 short strings.Each decimal place is spelled independently, and each digit 0–9 has one fixed spelling for its place. Precompute four small tables (thousands, hundreds, tens, ones) and concatenate the entries picked by the four digits of num. No loops over symbols at all.
- thousands = ["", "M", "MM", "MMM"].
- hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]; tens and ones follow the same shape with X/L/C and I/V/X.
- Return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10].
class Solution {
private static final String[] THOUSANDS = { "", "M", "MM", "MMM" };
private static final String[] HUNDREDS = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
private static final String[] TENS = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
private static final String[] ONES = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
public String intToRoman(int num) {
return THOUSANDS[num / 1000] + HUNDREDS[num / 100 % 10] + TENS[num / 10 % 10] + ONES[num % 10];
}
}class Solution:
THOUSANDS = ["", "M", "MM", "MMM"]
HUNDREDS = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
TENS = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
ONES = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
def intToRoman(self, num: int) -> str:
return (self.THOUSANDS[num // 1000] + self.HUNDREDS[num // 100 % 10]
+ self.TENS[num // 10 % 10] + self.ONES[num % 10])class Solution {
public:
string intToRoman(int num) {
static const string thousands[] = {"", "M", "MM", "MMM"};
static const string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
static const string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
static const string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10];
}
};const THOUSANDS = ["", "M", "MM", "MMM"];
const HUNDREDS = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
const TENS = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
const ONES = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
function intToRoman(num) {
return THOUSANDS[Math.floor(num / 1000)] + HUNDREDS[Math.floor(num / 100) % 10]
+ TENS[Math.floor(num / 10) % 10] + ONES[num % 10];
}Edge cases to test
- The six subtractive forms: 4, 9, 40, 90, 400, 900
- Zeros in the middle, like 1009 = MIX
- The smallest value 1 and the largest value 3999 = MMMCMXCIX
- Repeated symbols, like 3 = III and 300 = CCC
Hints
Hint 1
Treat the six subtractive pairs (CM, CD, XC, XL, IX, IV) as extra symbols with their own values.
Hint 2
With those 13 symbols sorted from largest to smallest, always take the largest one that still fits.
Hint 3
Alternatively, each decimal digit maps to a fixed string for its place: thousands, hundreds, tens, ones.
FAQ
What is the best time complexity for Integer to Roman?
Optimal (one lookup per decimal digit) runs in O(1) time and O(1) extra space. Exactly four table lookups and one concatenation.
Which pattern does Integer to Roman use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Jump Game II, Jump Game, Can Place Flowers.
Is there a brute force solution for Integer to Roman?
Yes. Brute force (greedy over 13 symbols) takes O(1) time and O(1) space. List the 13 values that have their own spelling, from 1000 (M) down to 1 (I), including the subtractive pairs like 900 (CM) and 4 (IV).
Which edge cases should I test for Integer to Roman?
The six subtractive forms: 4, 9, 40, 90, 400, 900; Zeros in the middle, like 1009 = MIX; The smallest value 1 and the largest value 3999 = MMMCMXCIX; Repeated symbols, like 3 = III and 300 = CCC.