This EASY Coding Question is VERY Commonly Asked at FAANG! | Roman to Integer - Leetcode 13

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[NoName]

IVII isn't a valid Roman integer since you have to write it as short as possible and you can write it as VI

[nifegun]

Of the rule is really just "smaller before bigger means subtract" and thats true in all cases and you dont need fo worry about malformed inputs, you can dodge the check ahead by just running through it backwards and remembering the last thing you added, if its smaller subtract it.

[sunvaroya]

Easier way to see it is to add every letter or substract it if followed by a greater letter

[sushaanthsureshkumar]

You can go from right to left to handle it. In this way you don't need a look ahead

[simonharris]

I actually did this one for fun once. I used a table, and on top of the characters you've used here, I also put IV into the table with a value of 4, as well as the others; IX = 9, XL =40, XC = 90, etc. Once you do that, all the elements in the table will appear in a Roman numeral sequence in descending value order. so matching on say XC (90) means that you don't have to check an values >= XC again. So I added a pointer to the table, which was the element in the table to start at next time. This also allowed me to check for errors, like having and I character after an IV pair, which is not valid.

[__lifeline__]

Alternatively you can also iterate through the string backwards and whenever a Roman numeral is less than the number after it you can subtract it from the total. That way you don’t need to skip the value.

Learned this from my first ever interview which went wrong in pretty much every way imaginable. Still haunts my nightmares to this day 😭

[abhiyans]

An easier approach would be iterating the roman numeral from right to left and keeping track of the previous number(aka the number to the right)

If ur current number is less than previous, then subtract the roman numeral value from the output number.
Else add it to the output number.

[unlucky-]

Why do we also need to check if i<n-1 ?

[KamiKomplex]

Building on another comment, look at the possible valid subtract sequences. IV=4, XIV=14, IX=9, XL=40, XC=90 etc etc. 4s and 9s in the digits for base 10. Exposes some more interesting algorithms.

[wbio]

What about IVXCI, with a line above IV?

[xmoex]

Going from right to left the lookahead can be handled implicitly

[MT-cfms]

bro I've done it with a turing machine, doing it on python is so much easy

[ericli]

Why can’t you just go by elements? So if the ith element is less than the I+1, we can just subtract from our total by i, otherwise we add.

[EricRohlfs]

Cause in the workforce it's all day every day converting Roman numerals to ints. Difference between computer science and software engineering right here

[fruitfcker]

To save watchers some time, the question states that the input is a valid roman integer.

[glych]

In Swift language

func romanToInt(_ s: String) -> Int {
let romanDict: [Character: Int] = ["I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000]
var result = 0
var prevValue = 0

for char in s.reversed() {
if let value = romanDict[char] {
if value < prevValue {
result -= value
} else {
result += value
}
prevValue = value
}
}

return result
}

let romanNumeral = "XXIV"
// Output: 24

[asagiai]

This is an easy code but it is technically a trap.
Because it actually looks not only if you are good at coding but also if you know what you are coding.

[limken]

:( Why didmt I see this few weeks ago befor I got this question..though my was a variation not exactly this

[filix]

I had this question in the freecodecamp's certification question and I got...😅