Roman to Integer Conversion in DSA Go - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total = 0

↓

Read current Roman symbol

↓

Look ahead to next symbol

↓

Is current < next?

Yes→Subtract current value from total

↓

Add current value to total

↓

Move to next symbol

↓

Repeat until end of string

↓

Return total as integer

We read each Roman symbol, compare it with the next one, and decide to add or subtract its value to get the final integer.

Execution Sample

DSA Go

func value(r byte) int {
  switch r {
  case 'I': return 1
  case 'V': return 5
  case 'X': return 10
  case 'L': return 50
  case 'C': return 100
  case 'D': return 500
  case 'M': return 1000
  }
  return 0
}

func romanToInt(roman string) int {
  total := 0
  for i := 0; i < len(roman); i++ {
    val := value(roman[i])
    if i+1 < len(roman) && val < value(roman[i+1]) {
      total -= val
    } else {
      total += val
    }
  }
  return total
}

// Example usage:
// roman := "IX"
// result := romanToInt(roman)
// fmt.Println(result) // Output: 9

This code converts the Roman numeral "IX" to the integer 9 by adding or subtracting values based on the next symbol.

Execution Table

Step	Operation	Current Symbol	Next Symbol	Condition (current < next?)	Action	Total After Operation
1	Read symbol	I	X	True	Subtract 1	0 - 1 = -1
2	Read symbol	X	None	False	Add 10	-1 + 10 = 9
3	End	None	None	N/A	Return total	9

💡 Reached end of string, total is 9

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
total	0	-1	9	9
i	0	1	2	2
current_symbol	None	I	X	None
next_symbol	None	X	None	None

Key Moments - 3 Insights

Why do we subtract the value when the current symbol is less than the next?

Because in Roman numerals, a smaller value before a larger one means subtraction, as shown in step 1 where 'I' is less than 'X', so we subtract 1.

What happens when we reach the last symbol with no next symbol?

We always add the value of the last symbol since there is no next symbol to compare, as in step 2 where 'X' is added.

Why do we check the next symbol before deciding to add or subtract?

Checking the next symbol lets us know if the current value should be subtracted (if smaller) or added (if equal or larger), ensuring correct conversion.

Visual Quiz - 3 Questions

Look at the execution table, what is the total after processing the first symbol?

A -1

B 1

C 0

D 10

💡 Hint

Check the 'Total After Operation' column in step 1 of the execution table.

At which step does the condition 'current < next' become false?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'Condition (current < next?)' column in the execution table.

If the Roman numeral was "XI" instead of "IX", how would the total change after step 1?

A It would be 10

B It would be -10

C It would be 1

D It would be -1

💡 Hint

Think about the comparison between 'X' and 'I' and check the variable_tracker for total changes.

Concept Snapshot

Roman to Integer Conversion:
- Read each symbol left to right
- Compare current symbol value with next
- If current < next, subtract current value
- Else, add current value
- Sum all to get integer
- Return total at end

Full Transcript

This visual trace shows how to convert Roman numerals to integers by reading each symbol, comparing it with the next, and deciding whether to add or subtract its value. For example, in 'IX', 'I' is less than 'X', so we subtract 1 first, then add 10, resulting in 9. The process repeats until all symbols are processed, and the total is returned.

Practice

1. What is the value of the Roman numeral IX when converted to an integer?

easy

A. 6

B. 11

C. 19

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 integer value

   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 Go code snippets correctly initializes a map for Roman numeral values?

easy

A. romanMap := map[string]int{"I" = 1, "V" = 5, "X" = 10}

B. romanMap := map[int]string{1: "I", 5: "V", 10: "X"}

C. romanMap := map[string]int{"I": 1, "V": 5, "X": 10}

D. romanMap := map[string]int{I: 1, V: 5, X: 10}

Solution

1. Step 1: Check map key and value types

   The map should have string keys (Roman numerals) and int values (their integer equivalents). romanMap := map[string]int{"I": 1, "V": 5, "X": 10} uses map[string]int correctly.

2. Step 2: Verify syntax correctness

   romanMap := map[string]int{"I": 1, "V": 5, "X": 10} uses correct Go syntax with colon ':' to assign values. Options A and C have syntax errors, and B reverses key-value types.

3. Final Answer:

   romanMap := map[string]int{"I": 1, "V": 5, "X": 10} -> Option C

4. Quick Check:

   Correct map syntax uses colons and proper types [OK]

Hint: Use colon ':' for map key-value pairs in Go [OK]

Common Mistakes:

• Using '=' instead of ':' in map initialization
• Swapping key and value types
• Omitting quotes around string keys

3. What will be the output of the following Go code snippet?

func romanToInt(s string) int {
    romanMap := map[byte]int{'I': 1, 'V': 5, 'X': 10}
    total := 0
    for i := 0; i < len(s); i++ {
        if i+1 < len(s) && romanMap[s[i]] < romanMap[s[i+1]] {
            total -= romanMap[s[i]]
        } else {
            total += romanMap[s[i]]
        }
    }
    return total
}

fmt.Println(romanToInt("IV"))

medium

A. 6

B. 4

C. 9

D. Error

Solution

1. Step 1: Analyze the loop and subtraction logic

   The code subtracts the value if the current numeral is less than the next one, else adds it. For "IV", 'I' (1) < 'V' (5), so subtract 1, then add 5.

2. Step 2: Calculate total value

   Total = -1 + 5 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   IV = 4 using subtraction rule [OK]

Hint: Subtract when current < next numeral [OK]

Common Mistakes:

• Adding all values without subtraction
• Index out of range errors
• Confusing byte and string keys in map

4. The following Go function is intended to convert Roman numerals to integers. What is the bug?

func romanToInt(s string) int {
    romanMap := map[byte]int{'I': 1, 'V': 5, 'X': 10}
    total := 0
    for i := 0; i < len(s); i++ {
        if romanMap[s[i]] < romanMap[s[i+1]] {
            total -= romanMap[s[i]]
        } else {
            total += romanMap[s[i]]
        }
    }
    return total
}

medium

A. Missing check for i+1 < len(s) causing index out of range

B. Using map with byte keys instead of string keys

C. Incorrect subtraction logic for Roman numerals

D. Returning total before loop ends

Solution

1. Step 1: Identify loop boundary issue

   The code accesses s[i+1] without checking if i+1 is within string length, causing possible index out of range error.

2. Step 2: Explain fix

   Adding condition 'i+1 < len(s)' before accessing s[i+1] prevents runtime error.

3. Final Answer:

   Missing check for i+1 < len(s) causing index out of range -> Option A

4. Quick Check:

   Always check bounds before accessing next element [OK]

Hint: Check i+1 < len(s) before accessing s[i+1] [OK]

Common Mistakes:

• Ignoring string length check for next index
• Confusing byte and string keys (not a bug here)
• Incorrect subtraction logic (logic is correct)

5. Given the Roman numeral MCMXCIV, what integer does it convert to using the standard Roman to Integer rules?

hard

A. 1994

B. 1984

C. 2004

D. 1949

Solution

1. Step 1: Break down the numeral into parts

   M = 1000, CM = 900 (100 before 1000 means subtract 100), XC = 90 (10 before 100), IV = 4 (1 before 5).

2. Step 2: Sum all parts

   1000 + 900 + 90 + 4 = 1994.

3. Final Answer:

   1994 -> Option A

4. Quick Check:

   MCMXCIV = 1994 by adding and subtracting parts [OK]

Hint: Add values, subtract when smaller before larger [OK]

Common Mistakes:

• Adding all numerals without subtraction
• Misreading CM as 1100 instead of 900
• Ignoring subtraction pairs