DEV Community

Cover image for Solution: Roman to Integer

Solution: Roman to Integer

seanpgallivan on February 20, 2021

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 upv...
Collapse
 
usamahafeez0 profile image
UsamaHafeez0 • Edited

There is an issue here

but we can clear that by multiplying num by any number between 2 and 4 before comparing it to ans,

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

but we can clear that by multiplying num by number 3 or 4 before comparing it to ans,

I haven't seen any example to fail in case of 3 or 4.
Thanks

Collapse
 
seanpgallivan profile image
seanpgallivan

Thanks, and you're correct. Article has been updated.

Collapse
 
sainiteshb profile image
Sai Nitesh • Edited

Thank you for very detailed explanation.
But i didnt understand why u used 4 in the statement

if(4* num<ans) ans-=num;
Enter fullscreen mode Exit fullscreen mode

can u please explain

Collapse
 
seanpgallivan profile image
seanpgallivan

This part of the explanation covers the 4:

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 any number between 2 and 4 before comparing it to ans, since the numerals jump in value by increments of at least 5x.

Collapse
 
sainiteshb profile image
Sai Nitesh

Thank you so much, i got it cleared :)

Collapse
 
jake6868 profile image
Jake6868

why is it wrong when I put the test case with roman number :"CMDM"

Thread Thread
 
seanpgallivan profile image
seanpgallivan

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).

Thread Thread
 
jake6868 profile image
Jake6868

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.

Thread Thread
 
zx1986 profile image
張旭
Collapse
 
alfredosalzillo profile image
Alfredo Salzillo

Kind of a one-liner.
It's better to sum in reverse order.

const romanMap = {
  'I':1,
  'V':5,
  'X':10,  
  'L':50,
  'C':100,
  'D':500,
  'M':1000,
}
const roman = (v) => romanMap[v];
const romanToNumber = (s) => s
    .split('')
    .reverse()
    .map(roman)
    .reduce((
        sum,
        value,
        i,
        { [i - 1]: prev = 0 },
        ) => (sum + Math.sign(value - prev) || 1) * value), 0);
Enter fullscreen mode Exit fullscreen mode
Collapse
 
seanpgallivan profile image
seanpgallivan

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.

const romanMap = {
  'I':1,
  'V':5,
  'X':10,  
  'L':50,
  'C':100,
  'D':500,
  'M':1000,
}
const romanToNumber = s => Uint16Array.from(s, n => romanMap[n])
    .reverse()
    .reduce((sum,value) => sum + (value * 4 < sum ? -value : value));
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mochidaz profile image
Rahman

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.

use std::collections::HashMap;

macro_rules! hashmap {
    ($( $key: expr => $val: expr ),*) => {{
         let mut map = ::std::collections::HashMap::new();
         $( map.insert($key, $val); )*
         map
    }}
}

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let mut ans: i32 = 0;

        let map = hashmap!["I" => 1, "V" => 5, "X" => 10, "L" => 50, "C" => 100, "D" => 500, "M" => 1000];

        s.chars().rev().into_iter().for_each(|c| {
            let mut num = map.get(c.to_string().as_str()).unwrap();
            if 4 * num < ans {
                ans -= num;
            }
            else {
                ans += num;
            };
        });
        ans
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
t3chnicallyinclined profile image
t3chnicallyinclined • Edited

Thanks for the help, after digging into each method I found the following:

There's no need for: .into_iter() since the rev() method returns an interator
and num does not need to be mutable in this case.

So here would be a little leaner version:

use std::collections::HashMap;

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let mut ans: i32  = 0;

        let map = HashMap::from([
            ("I", 1),
            ("V", 5),
            ("X", 10),
            ("L", 50),
            ("C", 100),
            ("D", 500),
            ("M", 1000),
        ]);

        s.chars().rev().for_each(|c| {
            let num = map.get(c.to_string().as_str()).unwrap();

            if 4 * num < ans {
                ans -= num;
            }
            else {
                ans += num;
            };

        });
        ans
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
adolfsad profile image
SadAdolf

Never Underestimate the POWER OF IF ELSE MUHAHAHAHA

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let letters = s.split('');
    let letterreversered = [];
    let numerual = []
    for (let x = letters.length ;x >= 0 ;x--){
        if (letters[x] === 'I'){
            if (letters[x+1] == 'V' | letters[x+1] == 'X'){
                numerual.push(0)
                letterreversered.push(0)
            }
            else if (letters[x-1] == 'V' | letters[x-1] == 'X'){
                numerual.push(0)
                letterreversered.push(0)
            }
            else {
                numerual.push(1)
                letterreversered.push(1)
            }

        }
        else if (letters[x] === 'V'){
            if (letters[x-1] === 'I'){
                numerual.push(4)   
                letterreversered.push(4) 
            }else if (letters[x+1] === 'I') {
                if (letters[x+2]=== 'X' | letters[x+2]=== 'V'){
                    numerual.push(5)
                    letterreversered.push(5)
                }else {
                    numerual.push(6)
                    letterreversered.push(6)   
                }
                // numerual.push(5)
                // letterreversered.push(5)
            }else {
                numerual.push(5)
                letterreversered.push(5)
            }

        }
        else if (letters[x] === 'X'){
            if (letters[x-1] === 'I'){
                numerual.push(9)  
                letterreversered.push(9)  
            }else if (letters[x+1] === 'L' | letters[x+1] === 'C' ) {
                numerual.push(0)
                letterreversered.push(0)
            }else if (letters[x+1] === 'I') {
                if (letters[x+2]=== 'X' | letters[x+2]=== 'V'){
                    numerual.push(10)
                    letterreversered.push(10)
                }else {
                    numerual.push(11)
                    letterreversered.push(11)   
                }
            }else {
                numerual.push(10)
                letterreversered.push(10)
            }
        }
        else if (letters[x] === 'L'){
            if (letters[x-1] === 'X'){
                numerual.push(40)   
                letterreversered.push(40) 
            }
            else {
                numerual.push(50)
                letterreversered.push(50)
            }

        }
        else if (letters[x] === 'C'){
            if (letters[x-1] === 'X'){
                numerual.push(90)   
                letterreversered.push(90) 
            }else if (letters[x+1] === 'M' | letters[x+1] === 'D' ) {
                numerual.push(0)
                letterreversered.push(0)
            }
            else {
                numerual.push(100)
                letterreversered.push(100)
            }
        }
        else if (letters[x] === 'D'){
            if (letters[x-1] === 'C'){
                numerual.push(400)   
                letterreversered.push(400) 
            }
            else {
                numerual.push(500)
                letterreversered.push(500)
            }
        }
        else if (letters[x] === 'M'){
            if (letters[x-1] === 'C'){
                numerual.push(900)   
                letterreversered.push(900) 
            }
            else {
                numerual.push(1000)
                letterreversered.push(1000)
            }
        }
    }
    // label.innerText = letters
    // label.innerText = letterreversered
    const reducer = (accumulator, curr) => accumulator + curr;
    let finalsum = numerual.reduce(reducer)
    // sum.innerText = finalsum


    return finalsum
};
Enter fullscreen mode Exit fullscreen mode
Collapse
 
gaweki profile image
Andrel Karunia S

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:

  • number reduced if the next number bigger than current number
  • number added if next number is smaller than or equal the current number
Collapse
 
dalcio profile image
Dalcio
/**
 *
 * @param {string} s
 * @return {number}
 */

const romanToInt = function (s) {
  const roman = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };

  let num = 0;

  for (let index = 0; index < s.length - 1; index++) {
    const curr = roman[s[index]];
    const next = roman[s[index + 1]];
    if (curr >= next) {
      num += curr;
    } else {
      num -= curr;
    }
  }
  num += roman[s[s.length - 1]];

  return Math.abs(num);
};

const s = "MCMXCIV";

console.log(romanToInt(s));
Enter fullscreen mode Exit fullscreen mode
Collapse
 
prateekool109 profile image
Satyagraha

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...

Collapse
 
apoorav_misra profile image
Apoorav Misra

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;

Collapse
 
rahulgawade1000 profile image
Rahul Gawade • Edited

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;
}
}

Collapse
 
thefluxapex profile image
Ian Pride

Very impressive, you have me inspired to write this in Rust. I have actually considered doing this many years ago, but, of course, I never got around to it and forgot about it.

Collapse
 
seanpgallivan profile image
seanpgallivan

Awesome. Feel free to drop the code in the comments here if you do!!

Collapse
 
rahulgawade1000 profile image
Rahul Gawade

what do you think of mine one ?

Collapse
 
sahilrana101 profile image
benice

Image description

Collapse
 
alish_satani profile image
Alish Satani

It's wrong for "MDCCCLXXXIV" .
ans should be 1884 and it returns 1664.

Collapse
 
seanpgallivan profile image
seanpgallivan • Edited

Just checked and all four of my codeblocks are properly returning 1884 for that input. Can you copy and paste the code you're using?

Edit: Apparently this happened by using 2 as the multiplier instead of 3 or 4. The article has been updated to correct for this mistake.