Roman to Integer Conversion in DSA Python - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total=0 and index=0

↓

Read current Roman symbol

↓

Check if next symbol exists and is larger?

↓

Subtract current

↓

Move index by 2

Back to start if index < length↓

Return total

↩Back to start if index < length

We read each Roman symbol, decide to add or subtract based on the next symbol, then move forward until all symbols are processed.

Execution Sample

DSA Python

def romanToInt(s):
    values = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    total = 0
    i = 0
    while i < len(s):
        if i+1 < len(s) and values[s[i]] < values[s[i+1]]:
            total += values[s[i+1]] - values[s[i]]
            i += 2
        else:
            total += values[s[i]]
            i += 1
    return total

This code converts a Roman numeral string to an integer by adding or subtracting values based on symbol order.

Execution Table

Step	Operation	Index i	Current Symbol	Next Symbol	Condition (next larger?)	Action	Total	Visual State
1	Start	0	M	C	No	Add 1000	1000	M(1000)
2	Move i by 1	1	C	M	Yes	Add 900 (1000-100)	1900	M(1000) -> CM(900)
3	Move i by 2	3	X	C	Yes	Add 90 (100-10)	1990	M(1000) -> CM(900) -> XC(90)
4	Move i by 2	5	I	V	Yes	Add 4 (5-1)	1994	M(1000) -> CM(900) -> XC(90) -> IV(4)
5	Move i by 2	7	-	-	-	End	1994	Final total 1994

💡 Index i reached length of string, all symbols processed

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
total	0	1000	1900	1990	1994	1994
i	0	1	3	5	7	7

Key Moments - 3 Insights

Why do we check if the next symbol is larger before adding or subtracting?

Because Roman numerals use subtraction when a smaller symbol is before a larger one (like IV = 4). The execution_table rows 2, 3, and 4 show this check deciding to subtract current from next.

Why do we move the index by 2 when the next symbol is larger?

Because we process two symbols together as one number (like IV). The execution_table rows 2, 3, and 4 show i increasing by 2 after such pairs.

What happens if the next symbol does not exist or is not larger?

We simply add the value of the current symbol and move index by 1, as shown in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total after step 3?

A 1900

B 1990

C 1000

D 1994

💡 Hint

Check the 'Total' column in execution_table row 3

At which step does the index i move by 2 for the first time?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Action' and 'Index i' columns in execution_table rows 1 and 2

If the input was 'III', how would the index i change?

A Increase by 2 each time

B Stay the same

C Increase by 1 each time

D Increase by 3 each time

💡 Hint

Refer to variable_tracker for i increments when next symbol is not larger (like step 1)

Concept Snapshot

Roman to Integer Conversion:
- Read symbols left to right
- If next symbol is larger, subtract current from next and add result
- Move index by 2 when subtracting, else by 1
- Sum all values for final integer
- Handles special subtractive pairs like IV, IX, CM

Full Transcript

This visual trace shows how to convert Roman numerals to integers by reading each symbol and deciding whether to add or subtract based on the next symbol. We start with total zero and index zero. At each step, we check if the next symbol exists and is larger. If yes, we subtract the current symbol's value from the next and add that to total, moving index by two. Otherwise, we add the current symbol's value and move index by one. This continues until all symbols are processed. The example 'MCMXCIV' is traced step-by-step, showing total and index changes. Key moments clarify why we check the next symbol and how index moves. Quizzes test understanding of total values and index increments. The snapshot summarizes the conversion rules clearly.

Practice

1. What is the integer value of the Roman numeral IX?

easy

A. 11

B. 19

C. 6

D. 9

Solution

1. Step 1: Understand Roman numeral rules for subtraction

   In Roman numerals, when a smaller numeral appears before a larger one, it is subtracted. Here, I (1) is before X (10), so 1 is subtracted from 10.

2. Step 2: Calculate the value of IX

   10 - 1 = 9.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral is before larger one [OK]

Common Mistakes:

• Adding values instead of subtracting
• Confusing IX with XI
• Ignoring subtraction rule

2. Which of the following Python code snippets correctly initializes a dictionary mapping Roman numerals to integers?

easy

A. roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50}

B. roman_map = ['I': 1, 'V': 5, 'X': 10, 'L': 50]

C. roman_map = ('I' = 1, 'V' = 5, 'X' = 10, 'L' = 50)

D. roman_map = {I: 1, V: 5, X: 10, L: 50}

Solution

1. Step 1: Identify correct dictionary syntax in Python

   Python dictionaries use curly braces with key:value pairs, keys as strings must be quoted.

2. Step 2: Check each option

   roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} uses correct syntax with quotes and curly braces. Options A, B, and D use invalid syntax. roman_map = {I: 1, V: 5, X: 10, L: 50} uses unquoted keys which causes NameError.

3. Final Answer:

   roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} -> Option A

4. Quick Check:

   Correct dictionary syntax = roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50} [OK]

Hint: Use curly braces and quote keys for dictionaries [OK]

Common Mistakes:

• Using square brackets instead of curly braces
• Not quoting string keys
• Using assignment '=' inside dictionary

3. What is the output of the following Python code?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
    return total

print(roman_to_int('XIV'))

medium

A. 14

B. 16

C. 9

D. 11

Solution

1. Step 1: Trace the loop for input 'XIV'

   Characters: X(10), I(1), V(5). Loop index i from 0 to 2.
   i=0: X(10) < I(1)? No, add 10.
   i=1: I(1) < V(5)? Yes, subtract 1.
   i=2: V(5), no next char, add 5.

2. Step 2: Calculate total

   Total = 10 - 1 + 5 = 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   X(10) + IV(4) = 14 [OK]

Hint: Subtract if current < next numeral, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Off-by-one errors in loop
• Ignoring last character addition

4. The following code is intended to convert a Roman numeral string to an integer. What is the error?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10}
    total = 0
    for i in range(len(s)):
        if roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
    return total

print(roman_to_int('IX'))

medium

A. SyntaxError due to missing colon

B. KeyError because 'IX' is not in roman_map

C. IndexError due to accessing s[i + 1] without boundary check

D. Returns incorrect value 11 instead of 9

Solution

1. Step 1: Identify loop and index usage

   The loop runs from i=0 to len(s)-1. At last index i, accessing s[i+1] causes IndexError.

2. Step 2: Explain why error occurs

   For input 'IX' (length 2), when i=1, s[i+1] is s[2], which is out of range.

3. Final Answer:

   IndexError due to accessing s[i + 1] without boundary check -> Option C

4. Quick Check:

   Check index bounds before s[i+1] access [OK]

Hint: Always check index before accessing s[i+1] [OK]

Common Mistakes:

• Not checking index bounds in loops
• Assuming s[i+1] always exists
• Ignoring runtime errors

5. Given the Roman numeral string 'MCMXCIV', what integer does the following code return?

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev_value = 0
    for char in reversed(s):
        value = roman_map[char]
        if value < prev_value:
            total -= value
        else:
            total += value
        prev_value = value
    return total

print(roman_to_int('MCMXCIV'))

hard

A. 1494

B. 1994

C. 1949

D. 2094

Solution

1. Step 1: Understand reversed traversal and subtraction logic

   The code processes characters from right to left, subtracting if current value is less than previous.

2. Step 2: Trace values for 'MCMXCIV'

   Characters reversed: V(5), I(1), C(100), X(10), M(1000), C(100), M(1000)
   Calculate total:
   V=5 (add 5)
   I=1 < 5 subtract 1 (total=4)
   C=100 > 1 add 100 (total=104)
   X=10 < 100 subtract 10 (total=94)
   M=1000 > 10 add 1000 (total=1094)
   C=100 < 1000 subtract 100 (total=994)
   M=1000 > 100 add 1000 (total=1994)

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   MCMXCIV = 1994 [OK]

Hint: Traverse right to left, subtract if smaller than previous [OK]

Common Mistakes:

• Processing left to right without subtraction logic
• Confusing numeral values
• Missing reversed traversal step