## DEV Community is a community of 750,871 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Shivam Sharma

Posted on • Updated on

# Leetcode 12: Integer to Roman [Solution]

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

## Problem Statement

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

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

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:

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.

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

## Implementation

C++ Code:

``````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){
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:

Cover Image by Shawn Lee on Unsplash

## Discussion (1)

merryhere

Thanks for codes.
raj