Leetcode 12: Integer to Roman [Solution]
Tags: cpp, algorithms, leetcode, programming
Published: 2021-03-10 11:14:21


This question is really very much similar to the manual approach, so just do the same you do in real life to convert a number to roman but this time with code.

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Algorithm](#algo)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>


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 numeral, 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"

**Example 2:**

> **Input:** num = 4
**Output:** "IV"

**Example 3:**

> **Input:** num = 9
**Output:** "IX"

**Example 4:**

> **Input:** num = 58
**Output:** "LVIII"
**Explanation:** L = 50, V = 5, III = 3.

**Example 5:**

> **Input:** num = 1994
**Output:** "MCMXCIV"
**Explanation:** M = 1000, CM = 900, XC = 90 and IV = 4.

**Constraints:**

-   `1 <= num <= 3999`

---

## Explanation <a name="explanation"></a>
So any natural number can be converted into Roman Numeral but as the number goes bigger the roman representation gets longer. Firstly just have a look at the **constraints** part, So the problem statement is clear that we need to convert the numbers below 4000 only. So how do we convert a number to roman in real life? Just do the same here or a slightly modified version to make it faster.

---

## Solution <a name="solution"></a>

Roman Numerals are usually written in the form of Larger to Smaller Numeral and a character can be contiguously repeated by *3 times maximum* **eg.** `1=I`, `2=II`, `3=III` but `4!=IIII`, it's `4=IV`. So writing a numeral multiple times means we are adding those numerals but whenever a smaller numeral comes before a bigger numeral, it means that we need to subtract smaller numeral from the bigger one.
For example, `2`  is written as  `II` in Roman numeral, just two ones added together.  `12`  is written as `XII`, which is simply  `X + II` but `19` is written as `XIX` i.e. `X + IX`.

So the separate numerals of the number are added to form the complete numeral for the whole number. As in roman numeral, we write from larger to smaller to we'll first try to write the larger numeral first.
Let's understand that in this way, for example, we need to convert `8` so we'll try to write it as `5 + 3` which will result in `VIII` but if I don't try to go with the larger number first then I might write it as `3 + 5` i.e. `IIIV` which is wrong.

So it's clear we need to break the number in a way that we get the roman numeral for the bigger part first. To do this we can create an ordered map of `number -> roman numeral` and try to reduce the number in a way that we extract the biggest numeral from the number and when the number can't be written with the biggest numeral then we'll try the next biggest numeral. While extracting we'll be concatenating the numerals.

### Algorithm: <a name="algo"></a>
1. Create an ordered dictionary of integer to the roman numeral for 1 character and 2 characters (eg. 4,9, 40, etc) roman numerals ordered by numerical value descending.
2. Point to the first(largest) element of this dictionary.
3. while `num>0` repeat
	1. if `num` >= numerical value pointing by the pointer, then add the string for this numerical value to the answer and deduct this numerical value from the number.
	2. Else move the pointer forward to point to the next biggest value in the dictionary.
4. Return answer string.


**Time Complexity:**  `O(n)` 
**Space Complexity:** `O(1)`

---

## Implementation <a name="implementation"></a>

**C++ Code:**

```cpp
class Solution {
public:
    string intToRoman(int num) {
	    // Prepare ordered dictionary with array and pair
        pair<int,string> rmap[] = {
	        {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"}
        };
        
        // Initialize pointer to the beginning of the array
        int rptr = 0;
        string str="";
		// Loop till the number is above 0
        while(num){
	        // If numeric value at pointer is >= the number
            if(num>=(rmap[rptr]).first){
	            // Add numeral to the answer
                str += (rmap[rptr]).second;
                // subtract numeric value from the number
                num -= (rmap[rptr]).first;
            }
            else{
	            // Move pointer to the next biggest numeric value
                rptr++;
            }
        }
        return str;
    }
};
```

**Runnable C++ Code:**
{% replit @shivams136/Leetcode-12-Integer-to-roman %}

Cover Image by <a href="https://unsplash.com/@shawn99lee?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Shawn Lee</a> on <a href="/s/photos/roman-numeral?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>