Integer to Roman - Short & Simple LeetCode Solution
In our last article we solved Roman to Integer problem. Today let's discuss another leetcode problem Integer to Roman.
Problem Statement
Convert the given integer to a roman numeral. As we saw in our previous article, roman numerals are represented using seven different symbols as shown below:
Symbol | Value |
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
For example, in Roman numerals:
1 is written as I.
2 is written as II i.e. by adding two "ones" I+I together.
12 is written as XII which is X + II.
Number 27 is XXVII, which is XX + V + II.
Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting 1 from 5 (i.e. V - I). Similarly, 9 is written as IX i.e. X - I.
There are six such instances in roman numerals 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.
Note: For a quick recap of roman numerals you can refer this article.
Constraints:
1 <= num <= 3999
Examples
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.Solution
To solve this problem, we need to first extend the given roman to integer table to include all the exceptional cases. We also need to arrange the values in this table in decreasing order (we will see why this is needed in more detail later in this article). With these changes our new table would look like this:
1000 | M |
900 | CM |
500 | D |
400 | CD |
100 | C |
90 | XC |
50 | L |
40 | XL |
10 | X |
9 | IX |
5 | V |
4 | IV |
1 | 1 |
Now with the modified table in place let's see how we can convert a given integer value to roman numeral. next to map the given integer to roman numeral we break the given integer first and then map it to the respective roman numeral. We can break any given integer by dividing it with appropriate values.
For example, if 153 is the given integer, the corresponding roman value is CLIII. To get this, we first break 153 into 3 parts: 100, 50 and 3. Next, we map each of these parts into roman values i.e. 100 is mapped to C, 50 is mapped to L and 3 is mapped to III, which in turn gives us CLIII. Similarly, if 2024 is the given integer we break it into 2000, 20 and 4. This in roman numerals is MM, XX and IV respectively or MMXXIV.
I hope you get an idea of how we need to approach this problem statement. Now let's see how we can translate this logic into code. Below algorithm shows how we can do this through code.
Algorithm
Create a list/array to store the extended integer to roman mapping, let call it intToRomanList.
Store the integer to roman mapping in this list in decreasing order.
Create a variable, let's say result to store the final result.
Next, we traverse intToRomanList from start to end, and in each iteration, we perform the following steps:
Divide the given number with the integer from intToRomanList. This will give us the no. of times we have to append the roman numeral. Example, if num=2000, if we divide it with M or 1000 from intToRomanList we get 2000/1000 = 2. This 2 is an indication that we need to append two M's i.e. MM in order to make a 2000. We will store this in a variable called count.
Now, only if count is greater than 0 we need to append the corresponding roman numeral to the result variable. Example, if num=500, for intToRomanList values M:1000, count = (num / intToRomanList integer) = 500/1000 = 0, Therefore, we need not append it to the result variable. In the next iteration, intToRomanList key:value is 500:D, so, count = (num / intToRomanList integer) = 500/500 = 1, Now count is greater than 0, therefore we need to add it to result.
After this we mod num with intToRomanList integer value to process its remaining part.
Repeat a-c until we reach the end of intToRomanList.
Finally return the value in result variable.
I know this is a bit confusing 😁. To make it easier let me explain it with the help of an example.
Let's say num=2024. First step is to create a list, lets create a list and name it intToRomanList. We will fill the list with the following key value pairs/values:
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
Let's also declare a variable result and initialize it to "". Next traverse intToRomanList starting from the first pair 1000:M.
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
Now, divide num with the current intToRomanList integer value i.e. 1000. This will give us the count (i.e. no. of times we need to append the current roman numeral to result).
count = (num / intToRomanList integer) = (2024/1000) = 2
This indicates that we need to add the current roman numeral in intToRomanList which is M, twice to result. Therefore, we append result with MM. Now result=MM. Since 1000th place is now processed, we need to remove it from num, so mod it with 1000:
num = num % 1000 = 2024 % 1000 = 24
After this we move to the next pair in intToRomanList 900:CM.
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
Repeat the previous steps again:
count = (num / intToRomanList integer) = (24/900) = 0
Now since count=0, no need to append anything to result.
num = num % 900 = 24 % 900 = 24
Again, we move ahead in intToRomanList by one:
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
We follow the same procedure again:
count = 24/500 = 0,
hence result remains unchanged and,
num = 24 % 500 = 24.
In the same way count, result and num remain unchanged for 400:CD, 100:C, 90:XC, 50:L, 40:XL. So, let's skip to 10:X.
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
Now,
count = 24/10 = 2, therefore result = "MM" + "XX"= "MMXX"
num = 24 % 10 = 4.
For 9:IX and 5:V again count, result and num remain unchanged. Now when our iteration reaches 4:IV,
{1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I}
count = 4/4 = 1, therefore result = "MMXX" + "IV"= "MMXXIV"
num = 4 % 4 = 0.
We stop the iteration, after we process the last element in rMap 1:I and return whatever is present in result as the final result.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses:
Code
Go Solution
Python Solution
Java Solution
JavaScript Solution
C Solution
C++ Solution
C# Solution
Complexity Analysis
Time Complexity: O(1)
In this algorithm we iterate over a list of size 13, which does not depend on the input size of num. Inside the loop, it performs division and modulus operations, which are constant time operations.
The code where we append to result also runs in constant time because the maximum possible value of count is limited and does not have any considerable impact on time complexity.
Therefore, regardless of the value of num, the number of operations is bounded by a constant, leading to a time complexity of O(1).
Space Complexity: O(1)
The space complexity is also O(1) since the algorithm uses a fixed size list for its computation.
That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers.
If you found value in this article, we encourage you to subscribe to both our website and YouTube channel. Your support fuels our motivation to continue producing more insightful articles like this one in the future.
Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!
Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
