Roman to Integer Conversion in DSA C

Mental Model

Roman numerals are letters that represent values. We add or subtract these values to get the number.

Analogy: Think of Roman numerals like money coins. Usually, you add their values, but if a smaller coin is before a bigger coin, you subtract it like giving change.

R O M A N -> I N T E G E R

Example: M -> 1000
Example: IV -> 4 (5 - 1)

Letters: I(1) -> V(5) -> X(10) -> L(50) -> C(100) -> D(500) -> M(1000)

Dry Run Walkthrough

Input: Roman numeral: "MCMIV"

Goal: Convert "MCMIV" to its integer value 1904

Step 1: Read 'M' (1000), add 1000

Total = 1000

Why: Start with first letter value

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

Total = 1000 - 100 = 900

Why: Smaller before bigger means subtract

Step 3: Read 'M' (1000), add 1000

Total = 900 + 1000 = 1900

Why: Add value when current is not smaller than next

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

Total = 1900 - 1 = 1899

Why: Smaller before bigger means subtract

Step 5: Read 'V' (5), add 5

Total = 1899 + 5 = 1904

Why: Add last value

Result:

Total = 1904

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

int value(char r) {
    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;
        default: return 0;
    }
}

int romanToInt(char *s) {
    int total = 0;
    int i = 0;
    int len = strlen(s);
    while (i < len) {
        int curr = value(s[i]);
        int next = (i + 1 < len) ? value(s[i + 1]) : 0;
        if (curr < next) {
            total += (next - curr);  // subtract smaller before bigger
            i += 2;                // skip next as processed
        } else {
            total += curr;         // add current value
            i++;
        }
    }
    return total;
}

int main() {
    char roman[] = "MCMIV";
    int result = romanToInt(roman);
    printf("%d\n", result);
    return 0;
}

int curr = value(s[i]);

get current Roman numeral value

int next = (i + 1 < len) ? value(s[i + 1]) : 0;

get next Roman numeral value if exists

if (curr < next) {

check if smaller before bigger to subtract

total += (next - curr);

add difference for subtractive pair

i += 2;

skip next character as processed

} else {

otherwise add current value

total += curr;

add current value to total

i++;

move to next character

Output

1904

Complexity Analysis

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

Space: O(1) because we use fixed extra space for variables

vs Alternative: This is more efficient than checking all substrings or using maps repeatedly, as it processes characters in one pass

Edge Cases

Empty string

Returns 0 because no numerals to convert

DSA C

while (i < len) {

Single character like 'I'

Returns value of single numeral correctly

DSA C

total += curr;

Invalid characters

Returns 0 for invalid characters due to default case in value()

DSA C

default: return 0;

When to Use This Pattern

When you see a problem asking to convert Roman numerals to numbers, use the subtractive rule pattern where smaller values before bigger ones mean subtraction.

Common Mistakes

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

Mistake: Not skipping the next character after processing a subtractive pair
Fix: Increment index by 2 when subtractive pair is processed

Summary

Converts Roman numeral strings to integer values by adding or subtracting letter values.

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

Remember smaller numeral before bigger means subtract, otherwise add.