Roman to Integer Conversion in DSA C#

Mental Model

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

Analogy: Think of reading a price tag where some discounts apply if a smaller number comes before a bigger number, so you subtract instead of add.

Roman numeral: M -> C -> M -> X -> C -> I -> V -> null
Values:    1000 -> 100 -> 1000 -> 10 -> 100 -> 1 -> 5 -> null
Pointer:   ↑

Dry Run Walkthrough

Input: Roman numeral: "MCMXCIV"

Goal: Convert the Roman numeral to its integer value 1994

Step 1: Read 'M' (1000), next is 'C' (100), since 100 < 1000, add 1000

Total = 1000

Why: Add value when current is greater or equal to next

Step 2: Read 'C' (100), next is 'M' (1000), since 100 < 1000, subtract 100

Total = 1000 - 100 = 900

Why: Subtract when current is less than next

Step 3: Read 'M' (1000), next is 'X' (10), since 1000 > 10, add 1000

Total = 900 + 1000 = 1900

Why: Add when current is greater or equal to next

Step 4: Read 'X' (10), next is 'C' (100), since 10 < 100, subtract 10

Total = 1900 - 10 = 1890

Why: Subtract when current is less than next

Step 5: Read 'C' (100), next is 'I' (1), since 100 > 1, add 100

Total = 1890 + 100 = 1990

Why: Add when current is greater or equal to next

Step 6: Read 'I' (1), next is 'V' (5), since 1 < 5, subtract 1

Total = 1990 - 1 = 1989

Why: Subtract when current is less than next

Step 7: Read 'V' (5), no next, add 5

Total = 1989 + 5 = 1994

Why: Add last value

Result:

Total integer value = 1994

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class RomanToIntegerConverter
{
    private static readonly Dictionary<char, int> romanMap = new Dictionary<char, int>
    {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

    public static int RomanToInt(string s)
    {
        int total = 0;
        for (int i = 0; i < s.Length; i++)
        {
            int currentVal = romanMap[s[i]];
            int nextVal = (i + 1 < s.Length) ? romanMap[s[i + 1]] : 0;

            if (currentVal < nextVal)
            {
                total -= currentVal; // subtract when smaller before larger
            }
            else
            {
                total += currentVal; // add otherwise
            }
        }
        return total;
    }

    static void Main()
    {
        string roman = "MCMXCIV";
        int result = RomanToInt(roman);
        Console.WriteLine(result);
    }
}

int currentVal = romanMap[s[i]];

Get integer value of current Roman character

int nextVal = (i + 1 < s.Length) ? romanMap[s[i + 1]] : 0;

Get integer value of next Roman character or 0 if none

if (currentVal < nextVal) { total -= currentVal; // subtract when smaller before larger } else { total += currentVal; // add otherwise }

Subtract if current is less than next, else add

Output

1994

Complexity Analysis

Time: O(n) because we scan the string once from left to right

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 regex, which can be slower and more complex

Edge Cases

Empty string

Returns 0 since no characters to process

DSA C#

int nextVal = (i + 1 < s.Length) ? romanMap[s[i + 1]] : 0;

Single character like 'V'

Returns the value of that character (5)

DSA C#

int nextVal = (i + 1 < s.Length) ? romanMap[s[i + 1]] : 0;

All characters in descending order like 'MDCLXVI'

All values added, no subtraction

DSA C#

if (currentVal < nextVal)

When to Use This Pattern

When you see a problem asking to convert Roman numerals to integers, use the subtractive rule pattern by comparing current and next values to decide add or subtract.

Common Mistakes

Mistake: Always adding values without checking if a smaller numeral comes before a larger one
Fix: Add a condition to subtract when current numeral is less than the next numeral

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 appears before a larger one, otherwise add.

Practice

1. What is the main rule to convert Roman numerals to integers?

easy

A. Subtract all values from the largest symbol

B. Multiply values of all symbols

C. Add values of symbols, subtract if a smaller symbol is before a larger one

D. Add values only if symbols are in alphabetical order

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals add values unless a smaller symbol is before a larger one, then subtract.

2. Step 2: Apply rule to conversion

   When converting, add values normally but subtract when a smaller symbol precedes a larger one.

3. Final Answer:

   Add values of symbols, subtract if a smaller symbol is before a larger one -> Option C

4. Quick Check:

   Roman numeral conversion rule = Add values of symbols, subtract if a smaller symbol is before a larger one [OK]

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

Common Mistakes:

• Multiplying values instead of adding/subtracting
• Ignoring subtraction rule
• Adding all values without checking order

2. Which C# code snippet correctly initializes a dictionary for Roman numeral values?

easy

A. var map = new Dictionary { {'I', 1}, {'V', 5} };

B. var map = new Dictionary { {1, 'I'}, {5, 'V'} };

C. var map = new Dictionary { {'I', 1}, {'V', 5} };

D. var map = new Dictionary { {'I', "1"}, {'V', "5"} };

Solution

1. Step 1: Identify correct dictionary types

   Roman numerals are characters mapped to integer values, so Dictionary is correct.

2. Step 2: Check initialization syntax

   Initialization with curly braces and pairs like {'I', 1} is correct syntax in C#.

3. Final Answer:

   var map = new Dictionary { {'I', 1}, {'V', 5} }; -> Option A

4. Quick Check:

   Dictionary with correct pairs = var map = new Dictionary { {'I', 1}, {'V', 5} }; [OK]

Hint: Use Dictionary for Roman numeral mapping [OK]

Common Mistakes:

• Swapping key and value types
• Using string keys instead of char
• Incorrect initialization syntax

3. What is the output of this C# code snippet?

string s = "IX";
var map = new Dictionary { {'I', 1}, {'V', 5}, {'X', 10} };
int result = 0;
for (int i = 0; i < s.Length; i++) {
  if (i + 1 < s.Length && map[s[i]] < map[s[i + 1]]) {
    result -= map[s[i]];
  } else {
    result += map[s[i]];
  }
}
Console.WriteLine(result);

medium

A. 9

B. 11

C. 6

D. 1

Solution

1. Step 1: Analyze loop and conditions

   For 'IX', at i=0: 'I' < 'X' so subtract 1; at i=1: add 10.

2. Step 2: Calculate result

   result = -1 + 10 = 9.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when current < next symbol, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Off-by-one errors in loop
• Incorrect dictionary values

4. Find the error in this C# code for Roman to integer conversion:

var map = new Dictionary { {'I', 1}, {'V', 5}, {'X', 10} };
int result = 0;
for (int i = 0; i < s.Length - 1; i++) {
  if (map[s[i]] < map[s[i + 1]]) {
    result -= map[s[i]];
  } else {
    result += map[s[i]];
  }
}
result += map[s[s.Length - 1]];
Console.WriteLine(result);

medium

A. No error, code works correctly

B. Missing initialization of string s

C. Loop should run till i < s.Length, not s.Length - 1

D. Dictionary keys should be strings, not chars

Solution

1. Step 1: Check variable declarations

   The variable 's' is used but not declared or initialized, causing a compile error.

2. Step 2: Verify loop and dictionary usage

   Loop and dictionary usage are correct; only 's' is missing.

3. Final Answer:

   Missing initialization of string s -> Option B

4. Quick Check:

   Undefined variable s causes error = Missing initialization of string s [OK]

Hint: Always declare and initialize variables before use [OK]

Common Mistakes:

• Forgetting to declare input string
• Incorrect loop range causing index errors
• Wrong dictionary key types

5. Given the Roman numeral string "MCMXCIV", what integer does the following C# code output?

string s = "MCMXCIV";
var map = new Dictionary {
  {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
};
int result = 0;
for (int i = 0; i < s.Length; i++) {
  if (i + 1 < s.Length && map[s[i]] < map[s[i + 1]]) {
    result -= map[s[i]];
  } else {
    result += map[s[i]];
  }
}
Console.WriteLine(result);

hard

A. 1494

B. 1904

C. 2000

D. 1994

Solution

1. Step 1: Break down the Roman numeral "MCMXCIV"

   M=1000, CM=900, XC=90, IV=4; sum = 1000 + 900 + 90 + 4.

2. Step 2: Calculate total value using code logic

   Code subtracts smaller before larger and adds others: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option D

4. Quick Check:

   MCMXCIV = 1994 [OK]

Hint: Sum values, subtract when smaller precedes larger [OK]

Common Mistakes:

• Adding all values without subtraction
• Misreading compound numerals like CM or XC
• Incorrect dictionary values