Introduction
In the last article, we saw how to convert Roman numbers to numeric values. In this article we will do exactly the opposite.
This is leetcode's problem number 12 with difficulty level set to medium. What we did last time is to compare current and next roman characters and perform basic addition and subtraction.
This problem is almost similar with a little extra space. What do I mean by extra space? Well, let's see.
The problem
Here is the problem straight out of Leetcode:
Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numerals, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used,
- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.
Example 1:
Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.
Example 2:
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
The Logic
There are 2 approaches to the solution. The first one with O(n*m) complexity and second one with O(n). Let's see both.
First Approach
The data structure we need for this problem is Dictionary because we need to store Key-Value pairs. Earlier I mentioned we need extra space. We need that extra space to handle these 6 conditions, IV, IX, XL, XC, CD, CM.
We can either use if else statements or switch cases to handle these conditions or simply add these values in the data structure as below.
Dictionary < string, int > romanNumbersDictionary = new() {
{
"I",
1
}, {
"IV",
4
}, {
"V",
5
}, {
"IX",
9
}, {
"X",
10
}, {
"XL",
40
}, {
"L",
50
}, {
"XC",
90
}, {
"C",
100
}, {
"CD",
400
}, {
"D",
500
}, {
"CM",
900
}, {
"M",
1000
}
};
Listing 1: Roman to Numbers dictionary
For logic all we have to do is to loop through the dictionary in reverse order from large to small number.
Tip: You can save dictionary values stored in reverse order, here just for demonstration I am using the Reverse() method of dictionary.
For each item in the dictionary we need to compare the number and shrink the number with every iteration.
For example, let's take 350 as input,
- We will traverse the dictionary in reverse order
- Compare 350 with each value of the dictionary until we find a value that is less than 350. That will take us to 100 from there we will start shrinking the number 350 till 350 becomes less than next value of dictionary.
- That will take 3 rounds of 100, i.e. 100 * 3 = "CCC", Now we are left with 50 for which we traverse further down till we find 50 and now we shrink 50.
- Concatenate "L" to the result. So our final result would be CCCL.
- We'll check if the number is <= 0 if yes then break the loop and return the result.
To understand the flow of execution, refer to this flowchart below. For example, we are using 1994. You can find how we are updating numbers with each iteration.
![]()
Figure 1: Flow chart for Integer to Roman
Once you understand the logic code is pretty straightforward.
internal class NumbersToRoman {
public string IntToRoman(int num) {
string romanResult = "";
Dictionary < string, int > romanNumbersDictionary = new() {
{
"I",
1
}, {
"IV",
4
}, {
"V",
5
}, {
"IX",
9
}, {
"X",
10
}, {
"XL",
40
}, {
"L",
50
}, {
"XC",
90
}, {
"C",
100
}, {
"CD",
400
}, {
"D",
500
}, {
"CM",
900
}, {
"M",
1000
}
};
foreach(var item in romanNumbersDictionary.Reverse()) {
if (num <= 0) break;
while (num >= item.Value) {
romanResult += item.Key;
num -= item.Value;
}
}
return romanResult;
}
}
Listing 2: Approach1.cs, Time complexity of O(n * m), Space complexity of O(n)
![]()
Figure 2: First approach's success snapshot
Note: This solution is suggested because here you don't have to manually map keys with value. But here we have time complexity of O(n * m), with space complexity of O(n).
We can scale this solution to O(n) but the tradeoff would be to expand the space complexity. Let's do that, for which we need 2 arrays one to hold roman letters and another for numbers.
Second approach
public string IntToRoman(int num) {
string romanResult = string.Empty;
string[] romanLetters = {
"M",
"CM",
"D",
"CD",
"C",
"XC",
"L",
"XL",
"X",
"IX",
"V",
"IV",
"I"
};
int[] numbers = {
1000,
900,
500,
400,
100,
90,
50,
40,
10,
9,
5,
4,
1
};
int i = 0;
while (num != 0) {
if (num >= numbers[i]) {
num -= numbers[i];
romanResult += romanLetters[i];
} else {
i++;
}
}
return romanResult;
}
Listing 3: Approach 2, Time complexity of O(n), Space complexity of O(n + m)
In this solution, we have optimized the code with time complexity of O(n), but now space complexity is O(n+m).
![]()
Figure 3: Solution 2 success snapshot
It's up to you to choose your own adventure w.r.t. approach.
What I feel is, the second approach could lead to user error. I can easily mismatch elements in either of the arrays while typing. So I will have to keep track of key and value pairs to ensure each key is representing its own value.
For the scope of this problem it's okay as input is limited but if in future input is expanded then it could create a problem.
But that's the discussion for another day. Till then have a good one.