This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #13 (Easy): Roman to Integer
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Roman numerals are represented by seven different symbols:
I
,V
,X
,L
,C
,D
andM
.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example,
2
is written asII
in Roman numeral, just two one's added together.12
is written asXII
, which is simplyX + II
. The number27
is written asXXVII
, which isXX + 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 asIV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written asIX
. There are six instances where subtraction is used:
I
can be placed beforeV
(5
) andX
(10
) to make4
and9
.X
can be placed beforeL
(50
) andC
(100
) to make40
and90
.C
can be placed beforeD
(500
) andM
(1000
) to make400
and900
.Given a roman numeral, convert it to an integer.
Examples:
Example 1: Input: s = "III" Output: 3
Example 2: Input: s = "IV" Output: 4
Example 3: Input: s = "IX" Output: 9
Example 4: Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Example 5: Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s
contains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M')
.- It is guaranteed that
s
is a valid roman numeral in the range[1, 3999]
.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The only really tricky thing about counting in roman numerals is when a numeral is used as a subtractive value rather than an additive value. In "IV" for example, the value of "I", 1, is subtracted from the value of "V", 5. Otherwise, you're simply just adding the values of all the numerals.
The one thing we should realize about the subtractive numerals is that they're identifiable because they appear before a larger number. This means that the easier way to iterate through roman numerals is from right to left, to aid in the identifying process.
So then the easy thing to do here would be to iterate backwards through S, look up the value for each letter, and then add it to our answer (ans). If we come across a letter value that's smaller than the largest one seen so far, it should be subtracted rather than added.
The standard approach would be to use a separate variable to keep track of the highest value seen, but there's an easier trick here. Since numbers generally increase in a roman numeral notation from right to left, any subtractive number must also be smaller than our current ans.
So we can avoid the need for an extra variable here. We do run into the case of repeated numerals causing an issue (ie, "III"), but we can clear that by multiplying num by either 3 or 4 before comparing it to ans, since the numerals jump in value by increments of at least 5x. (Note: 2 is too small of a multiplier due to the possibility of a triple character followed by another, ie: "XXXI" where 2 * 10 < 21)
Once we know how to properly identify a subtractive numeral, it's a simple matter to just iterate backwards through S to find and return the ans.
Implementation:
Javascript and Python both operate with objects / disctionaries quite quickly, so we'll use a lookup table for roman numeral values.
Java and C++ don't deal with objects as well, so we'll use a switch case to function much the same way.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
const roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
var romanToInt = function(S) {
let ans = 0
for (let i = S.length-1; ~i; i--) {
let num = roman[S.charAt(i)]
if (4 * num < ans) ans -= num
else ans += num
}
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
class Solution:
def romanToInt(self, S: str) -> int:
ans = 0
for i in range(len(S)-1,-1,-1):
num = roman[S[i]]
if 4 * num < ans: ans -= num
else: ans += num
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int romanToInt(String S) {
int ans = 0, num = 0;
for (int i = S.length()-1; i >= 0; i--) {
switch(S.charAt(i)) {
case 'I': num = 1; break;
case 'V': num = 5; break;
case 'X': num = 10; break;
case 'L': num = 50; break;
case 'C': num = 100; break;
case 'D': num = 500; break;
case 'M': num = 1000; break;
}
if (4 * num < ans) ans -= num;
else ans += num;
}
return ans;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int romanToInt(string S) {
int ans = 0, num = 0;
for (int i = S.size()-1; ~i; i--) {
switch(S[i]) {
case 'I': num = 1; break;
case 'V': num = 5; break;
case 'X': num = 10; break;
case 'L': num = 50; break;
case 'C': num = 100; break;
case 'D': num = 500; break;
case 'M': num = 1000; break;
}
if (4 * num < ans) ans -= num;
else ans += num;
}
return ans;
}
};
Top comments (25)
There is an issue here
as the algo will produce incorrect result when num is multiplied by 2. As Alish Satani (i tried but couldn't mention idk how to :P) commented that this algo produces wrong results on "MDCCCLXXXIV" this roman.
It returns 1664 while the correct answer is 1884. This only happens when num is multiplied by 2.
Dry Run:
Let's try a little dry run (MDCCCLXXXIV):
num = ans = 0;
Starting from right side
We read V: 5 * 2 < 0 (ans initially is 0) = false, so ans becomes 5
Next we read I: 1 * 2 < 5 = true, so we subtract 1 from 5 and ans = 4 now
Next we read X: 10 * 2 < 4 = false, we add 10 to ans, ans = 14
Again we get X: 10 * 2 < 14 = false, we add 10 to ans, ans = 24
Here is the issue we get X again (3rd consecutive): 10 * 2 < 24 "TRUE", now we remove 10 from 24 instead of adding it.
So the trouble begins when the algo encounters same roman element for 3 consecutive times in case we multiply it with 2. You can see this pattern to repeat again in case of DCCCL (3 Cs).
Reason:
Reason for this is as the roman elements can be repeated upto max 3 consecutive times so the sum of all romans on its right side are going to be less then 3 times of the the repeating roman. Like in case of XXX the sum of romans on the right is going to be less then 3 * 10 but when we use 2 as a constant then we don't account for the possibility of 3rd consecutive roman and like in case of XXX 2 * 10 is not less then XXIV (or XX.....).
FIX:
so, the article should say
I haven't seen any example to fail in case of 3 or 4.
Thanks
Thanks, and you're correct. Article has been updated.
Thank you for very detailed explanation.
But i didnt understand why u used 4 in the statement
can u please explain
This part of the explanation covers the 4:
Thank you so much, i got it cleared :)
why is it wrong when I put the test case with roman number :"CMDM"
Because that's not a valid Roman numeral sequence. Roman numbers are written in descending value order, with the exception for 9s and 4s and their equivalents in orders of magnitude.
At the start, the "CM" would be read as 900, because "C" is 100 and "M" is 1000. But then you have a "D", which would be another 500, so "CMD" would be 1400. But you'd never write it that way instead of "MCD" which is 1000+400 (rather than 900+500).
Then you have another "M", which is another 1000, but then that "M" should go at the beginning.
So assuming that the "CM" is supposed to be 900 (rather than 1100), then this should be written as "MMCD", or 1000+1000+400 (M+M+CD).
what do you mean by "with the exception for 9s and 4s and their equivalents in orders of magnitude." I don't understand the "s" meaning and why "9s" and "4s". Sorry, if you have time can you explain to me.
you could check the dev.to/seanpgallivan/solution-inte...
Kind of a one-liner.
It's better to sum in reverse order.
The one-liners are never quite as performant as the more standard code, but I do love one-line solutions!
Suggestions: You can simplify/speed up the solution a bit by condensing the .split() and .map(), while converting to a faster 16-bit typed array with Uint16Array.from(). Then, you can also simplify the .reduce() a bit as well.
This one's written in Rust. Used macro rules for hashmap so that i won't have to insert all the romans and their values one by one into the hashmap.
Thanks for the help, after digging into each method I found the following:
There's no need for:
.into_iter()
since therev()
method returns an interatorand
num
does not need to be mutable in this case.So here would be a little leaner version:
Never Underestimate the POWER OF IF ELSE MUHAHAHAHA
hello there
i have not checked yet the speed, but this accepted
Javascript solution:
var romanToInt = function(s) {
const roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
let ans = 0
for(let i = 0; i < s.length; i++){
if(roman[s[i]] < roman[s[i+1]]){
ans -= roman[s[i]]
} else {
ans += (roman[s[i]] || 0) // still accepted using zero or not
}
}
return ans
};
Idea:
Simple Explanation | Java code with detailed comments
Simple Explanation video - youtu.be/iOjKZ4_xQPM
Java code with detailed comments in repository - github.com/prateekgoyal511/dsa/blo...
public static int romanToInt(String s){
int year = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c == 'I') {
if (i != s.length() - 1 && s.charAt(i + 1) == 'V')
year = year - 1;
else if (i != s.length() - 1 && s.charAt(i + 1) == 'X')
year = year - 1;
else
year = year + 1;
}
else if(c == 'V')
year = year + 5;
else if(c == 'X'){
if (i != s.length() - 1 && s.charAt(i + 1) == 'L')
year = year - 10;
else if (i != s.length() - 1 && s.charAt(i + 1) == 'C')
year = year - 10;
else
year = year + 10;
}
else if(c == 'L')
year = year + 50;
else if(c == 'C'){
if (i != s.length() - 1 && s.charAt(i + 1) == 'D')
year = year - 100;
else if (i != s.length() - 1 && s.charAt(i + 1) == 'M')
year = year - 100;
else
year = year + 100;
}
else if(c =='D')
year = year + 500;
else if(c == 'M')
year = year + 1000;
}
return year;
I did traverse Left to right. Its Accepted .
class Solution {
public int romanToInt(String s) {
Map map=new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
char [] romanChar=s.toCharArray();
int sum=0;
int i=0;
for(char ch:romanChar){
int flag=1;
if(!(i==s.length()-1) ){
if (map.get(ch) < map.get(s.charAt(i + 1))) {
sum = sum - map.get(ch) ;
flag=0;
}
}
if(flag==1) {
sum = sum + map.get(ch);
}
i++;
}
return sum;
}
}