Roman to Integer
Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. The symbols are written from largest to smallest and added up, except in six subtractive pairs where a smaller symbol comes first and is taken away from the larger one: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900.
You get a valid Roman numeral s. Return the integer it stands for.
Function
- sstring
- a valid Roman numeral in capital letters
- Returnsinteger
- the value of the numeral, from 1 to 3999
Constraints
1 ≤ s.length ≤ 15scontains only the charactersI,V,X,L,C,DandM.sis a valid Roman numeral for a value from 1 to 3999.
Examples
- Input
- s = "XXVII"
- Output
- 27
- Explanation
XXis 10 + 10,Vis 5 andIIis 1 + 1, so the total is 27. No symbol is followed by a larger one, so every symbol is added.
- Input
- s = "CDXLIV"
- Output
- 444
- Explanation
- The numeral is three subtractive pairs in a row:
CDis 400,XLis 40 andIVis 4, which makes 444.
- Input
- s = "MCDXCII"
- Output
- 1492
- Explanation
Mis 1000,CDis 400,XCis 90 andIIis 2, so the numeral is 1492. Pairs and plain symbols mix freely.
+22 hidden tests on Submit
Follow-up
Can you write the reverse, turning an integer from 1 to 3999 into its Roman numeral?
Hints
Open them one at a time. Each one gives away a little more.
Write the numeral out as one value per symbol.
MCDXCIIbecomes 1000, 100, 500, 10, 100, 1, 1. Which of those values should count as negative so that the sum comes out to 1492?A symbol is subtracted exactly when the symbol right after it is worth more: the C in
CD, the X inXC. Every other symbol is added, including a symbol followed by an equal one, as inII.Walk the string once with an index. Compare the current symbol's value with the next symbol's value, subtract the current one if it is smaller and add it otherwise. The last symbol has no neighbor, so it is always added.
Solution
Most of a numeral is a plain sum, so the whole problem is spotting the six subtractive pairs. You can look them up as two-letter tokens, or use the one rule that covers all six: a symbol worth less than its right neighbor is subtracted. Either way, one pass over at most 15 characters gives the answer.
Read subtractive pairs as tokens
Intuition
Think of the numeral as a row of tokens. Most tokens are one symbol, and six are two symbols: IV, IX, XL, XC, CD and CM. Cut the string into those tokens, add up their values, and you have the number.
At each position, look at the next two characters first. If they form one of the six pairs, add the pair's value and step over both. Otherwise add the value of the single symbol and step over one. MCDXCII splits into M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.
The pair check has to come first. If you read the X of XC on its own, you add 10 and then 100 and get 110 instead of 90. The check is also safe: in a valid numeral a smaller symbol stands right before a larger one only inside one of these six pairs, so every pair you find is a real one.
Each step consumes one or two characters, so the loop runs at most 15 times. The two tables have a fixed size, so the extra space is constant.
Algorithm
- Make one table for the six pairs and one for the seven single symbols.
- Start at index 0 with a total of 0.
- If the two characters at the index form a pair, add the pair's value and move the index by 2.
- Otherwise add the single symbol's value and move the index by 1.
- When the index passes the end, return the total.
def romanToInt(s):
pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
i = 0
while i < len(s):
two = s[i:i + 2]
if two in pairs:
total += pairs[two]
i += 2
else:
total += singles[s[i]]
i += 1
return totalCompare each symbol with the next one
Intuition
Look at the six pairs again. In every one, the first symbol is worth less than the second, and the pair is worth the second minus the first. So you can drop the pair table and use one rule: if a symbol is worth less than the symbol to its right, subtract it; otherwise add it. CM becomes -100 + 1000 = 900, the same value the token reading gives.
Walk through MCDXCII. M is followed by a smaller C, so add 1000. C is followed by a larger D, so subtract 100: the total is 900. Add D to reach 1400. X is followed by a larger C, so subtract 10: 1390. Add C: 1490. The first I is followed by an equal I, so add it: 1491. The last I has no neighbor, so add it too: 1492.
The comparison must be strictly less than. Equal neighbors are always added, which is what makes II 2 and XX 20. The rule is correct for the same reason the token reading is: in a valid numeral, a smaller symbol comes right before a larger one only as the first half of a subtractive pair.
You look at each character once and keep one running total, so the time is O(n) and the extra space is O(1). This version needs only the seven symbol values and one comparison per character.
Algorithm
- Store the value of each of the seven symbols.
- Loop over the indices of
swith a running total that starts at 0. - If the next symbol exists and is worth more than the current one, subtract the current value.
- Otherwise add the current value.
- Return the total after the loop.
def romanToInt(s):
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
value = values[s[i]]
# A symbol worth less than the one after it is subtracted, like the I in IV.
if i + 1 < len(s) and value < values[s[i + 1]]:
total -= value
else:
total += value
return total
Pitfalls and edge cases
The rule is short, so the mistakes are about the edges of it.
- Using less than or equal instead of strictly less than. Then
IIcomes out as 0 andXXas 0, because each first symbol is subtracted. - Reading the next symbol on the last character.
s[i+1]does not exist there; checki+1against the length first, and always add the last symbol. - In the token version, trying single symbols before pairs.
XCthen reads as 10 + 100 = 110. - Spotting the pair only at its second symbol. If you have already added the I of
IV, you have to take it away twice,1 + 5 - 2 × 1= 4. Comparing with the next symbol avoids that correction. - Forgetting that Lua and R strings start at index 1, so the last symbol is at
#sornchar(s).
Frequently asked questions4
What is the time complexity of Roman to Integer?
Both approaches read each character once, so the time is O(n) for a numeral of n characters. The extra space is O(1), because the lookup tables have a fixed size. A numeral from 1 to 3999 has at most 15 characters, so in practice the work is tiny.
Why do you subtract a symbol that is smaller than the next one?
That is how the six subtractive pairs are built. In IV, IX, XL, XC, CD and CM, a smaller symbol comes before a larger one and the pair is worth the larger minus the smaller. Subtracting the first symbol and adding the second gives exactly that value, and no other place in a valid numeral has a smaller symbol before a larger one.
Can you convert a Roman numeral from right to left?
Yes. Walk from the last symbol to the first and remember the value of the symbol you read before, the one to the right. If the current symbol is worth less than that one, subtract it; otherwise add it. It is the same rule as the left to right version, seen from the other side.
Does this solution check that the numeral is valid?
No. The problem promises a valid numeral, so the code only adds and subtracts. Given an invalid string such as IIII or VV it still returns a number, 4 and 10. To validate, convert the result back to a numeral and compare it with the input.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def romanToInt(s):
# Write code hereCase 1
Case 2
Case 3
Input
s = "XXVII"
Expected
27