DSA Tracker

Visualize

Roman to Integer

Left-to-right scan with subtractive notation

time O(n)space O(1)

Scan left to right. If the current roman value is less than the next value, subtract it (subtractive notation like IV=4, IX=9). Otherwise add it. This single pass computes the total.

Details

Animated on: Given roman="MCMXCIV", convert to integer (1994)

Problem:Roman to IntegerEasy

Left-to-right scan with subtractive notation

step 1 / 8

M
[0]
C
[1]
M
[2]
X
[3]
C
[4]
I
[5]
V
[6]

i=0: s[0]='M', cur=1000. i+1<7 && 1000 < values[s[1]]=values['C']=100? No. Add cur: total=1000. Running total: 1000.

  • i=0· arr[0] = M
Pseudocode
1FUNCTION romanToInt(s):
2  values = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 }
3  total = 0
4  FOR i from 0 to length of s - 1:
5    cur = the value of roman letter s[i]
6    IF there is a next letter and cur < the value of s[i + 1]:
7      subtract cur from total
8    ELSE:
9      add cur to total
10    END IF
11  END FOR
12  RETURN total
13END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. i=0: s[0]='M', cur=1000. i+1<7 && 1000 < values[s[1]]=values['C']=100? No. Add cur: total=1000. Running total: 1000.
  2. i=1: s[1]='C', cur=100. i+1<7 && 100 < values[s[2]]=values['M']=1000? Yes. Subtract cur: total=1000-100=900. Running total: 900 (net effect: M=1000, C before M=900).
  3. i=2: s[2]='M', cur=1000. i+1<7 && 1000 < values[s[3]]=values['X']=10? No. Add cur: total=900+1000=1900. Running total: 1900 (CM=900 + M=1000).
  4. i=3: s[3]='X', cur=10. i+1<7 && 10 < values[s[4]]=values['C']=100? Yes — X before a bigger C means subtract now, the C at i=4 adds its full 100 next. total=1900-10=1890.
  5. i=4: s[4]='C', cur=100. i+1<7 && 100 < values[s[5]]=values['I']=1? No. Add cur: total=1890+100=1990. Running total: 1990 (MCMXC so far: M=1000, CM=900, XC=90, subtotal 1990).
  6. i=5: s[5]='I', cur=1. i+1<7 && 1 < values[s[6]]=values['V']=5? Yes. Subtract cur: total=1990-1=1989. Running total: 1989 (I before V = subtractive, IV=4 handling).
  7. i=6: s[6]='V', cur=5. No next character (i+1=7 >= 7). Add cur: total=1989+5=1994. Running total: 1994. Final answer.
  8. Answer: MCMXCIV = 1994. Breakdown: M=1000, CM=900, XC=90, IV=4. Total 1000+900+90+4=1994.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Roman to Integer in the editorAll Strings problemsBack to roadmap