Roman to Integer Conversion in DSA Go

Mental Model

Roman numerals are letters that represent values. We add or subtract these values based on their order to get the final number.

Analogy: Think of reading a price tag where some discounts apply if a smaller number comes before a bigger number, like 'IV' means 5 minus 1, not 1 plus 5.

R: I V X L C D M
V: 1 5 10 50 100 500 1000
Example: M -> 1000 -> [curr->C] -> 100 -> [curr->M] -> 1000

Dry Run Walkthrough

Input: Roman numeral: MCMIV

Goal: Convert the Roman numeral MCMIV to its integer value

Step 1: Read 'M' and add 1000

Total = 1000, next char = C

Why: Start with the first letter's value

Step 2: Compare 'C'(100) with next 'M'(1000), since 100 < 1000, subtract 100

Total = 1000 - 100 = 900, next char = M

Why: Smaller before bigger means subtract

Step 3: Read 'M'(1000) and add it

Total = 900 + 1000 = 1900, next char = I

Why: Add value when current is not smaller than next

Step 4: Compare 'I'(1) with next 'V'(5), since 1 < 5, subtract 1

Total = 1900 - 1 = 1899, next char = V

Why: Smaller before bigger means subtract

Step 5: Read 'V'(5) and add it

Total = 1899 + 5 = 1904, end of string

Why: Add last value

Result:

Total = 1904

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func romanToInt(s string) int {
	values := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	total := 0
	for i := 0; i < len(s); i++ {
		value := values[s[i]]
		if i+1 < len(s) && value < values[s[i+1]] {
			total -= value // subtract if smaller before bigger
		} else {
			total += value // else add
		}
	}
	return total
}

func main() {
	r := "MCMIV"
	result := romanToInt(r)
	fmt.Println(result)
}

values := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

map Roman letters to their integer values

for i := 0; i < len(s); i++ {

iterate over each character in the string

value := values[s[i]]

get integer value of current Roman numeral

if i+1 < len(s) && value < values[s[i+1]] {

check if current value is less than next to decide subtract or add

total -= value // subtract if smaller before bigger

subtract current value when smaller before bigger

total += value // else add

add current value otherwise

Output

1904

Complexity Analysis

Time: O(n) because we scan the Roman numeral string once

Space: O(1) because the map size is fixed and no extra space grows with input

vs Alternative: This is more efficient than checking all substrings or using recursion, which could be slower

Edge Cases

Empty string

Returns 0 as there are no numerals to convert

DSA Go

for i := 0; i < len(s); i++ {

Single character like 'V'

Returns the value of that single Roman numeral correctly

DSA Go

value := values[s[i]]

All same numerals like 'III'

Adds all values correctly without subtraction

DSA Go

if i+1 < len(s) && value < values[s[i+1]] {

When to Use This Pattern

When you see a problem converting Roman numerals to numbers, use the subtract-if-smaller-before-bigger pattern to handle special cases.

Common Mistakes

Mistake: Always adding values without checking the next numeral
Fix: Add a condition to subtract when current numeral is smaller than the next

Mistake: Not handling the last character properly
Fix: Ensure loop runs through all characters and adds the last one

Summary

Converts Roman numeral strings to integer values by adding or subtracting based on order.

Use when you need to interpret Roman numerals as numbers in code.

Remember to subtract when a smaller numeral comes before a larger one, otherwise add.

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