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
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 beforeV
(5) andX
(10) to make 4 and 9. -
X
can be placed beforeL
(50) andC
(100) to make 40 and 90. -
C
can be placed beforeD
(500) andM
(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:
- 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.
- Point to the first(largest) element of this dictionary.
- while
num>0
repeat- 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. - Else move the pointer forward to point to the next biggest value in the dictionary.
- if
- Return answer string.
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){
// 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:
Top comments (3)
Integrated Local Governance Management System is referred to by its acronym,ILGMS It is an electronic platform that integrates several services and operations to improve and expedite the administration of local governments. By offering a complete solution for managing municipal operations and services, this system seeks to increase effectiveness, transparency, and citizen participation in local governance.
Great explanation of Roman numerals! The subtraction principle is crucial for understanding numbers like IV and IX. It's fascinating how this system works. Knowing the six instances where subtraction is used makes reading and writing Roman numerals much easier. You can try to sso
Thanks for codes.
raj