Roman to Integer Conversion in DSA C++

Mental Model

Roman numerals are letters that represent numbers. We add or subtract values based on their order to find 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: M -> C -> X -> I -> V
Values: 1000 -> 100 -> 10 -> 1 -> 5
We read left to right, adding or subtracting values.

Dry Run Walkthrough

Input: Roman numeral: "MCMIV"

Goal: Convert the Roman numeral to its integer value.

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

Total = 1000

Why: Start with first symbol 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), next is 'I' (1), since 1000 > 1, add 1000

Total = 900 + 1000 = 1900

Why: Bigger or equal means add

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), no next symbol, add 5

Total = 1899 + 5 = 1904

Why: Last symbol always adds

Result:

Total integer value = 1904

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>

class RomanToInteger {
public:
    int romanToInt(const std::string& s) {
        std::unordered_map<char, int> values = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int total = 0;
        for (size_t i = 0; i < s.size(); ++i) {
            int current = values[s[i]];
            int next = (i + 1 < s.size()) ? values[s[i + 1]] : 0;
            if (current < next) {
                total -= current;  // subtract when smaller before bigger
            } else {
                total += current;  // add otherwise
            }
        }
        return total;
    }
};

int main() {
    RomanToInteger converter;
    std::string roman = "MCMIV";
    int result = converter.romanToInt(roman);
    std::cout << result << std::endl;
    return 0;
}

int current = values[s[i]];

Get value of current Roman symbol

int next = (i + 1 < s.size()) ? values[s[i + 1]] : 0;

Get value of next symbol or 0 if none

if (current < next) { total -= current; } else { total += current; }

Subtract if smaller before bigger, else add

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

Edge Cases

Empty string

Returns 0 as no symbols to convert

DSA C++

int next = (i + 1 < s.size()) ? values[s[i + 1]] : 0;

Single symbol like 'V'

Returns value of that symbol directly

DSA C++

if (current < next) { total -= current; } else { total += current; }

All symbols in descending order like 'MDCLXVI'

All values added, no subtraction

DSA C++

if (current < next) { total -= current; } else { total += current; }

When to Use This Pattern

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

Common Mistakes

Mistake: Always adding values without checking next symbol causes wrong totals for subtractive cases.
Fix: Check if current symbol is smaller than next and subtract in that case.

Summary

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

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

Remember to subtract when a smaller value 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. 11

B. 6

C. 9

D. 19

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 subtract 1 from 10.

2. Step 2: Calculate the integer value

   10 - 1 = 9.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral precedes larger one [OK]

Common Mistakes:

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

2. Which of the following C++ code snippets correctly initializes a map for Roman numeral values?

easy

A. std::map roman{{'I', 1}, {'V', 5}, {'X', 10}};

B. std::map roman = {'I':1, 'V':5, 'X':10};

C. std::map roman = {('I', 1), ('V', 5), ('X', 10)};

D. std::map roman = [('I', 1), ('V', 5), ('X', 10)];

Solution

1. Step 1: Check C++ map initialization syntax

   In modern C++, maps can be initialized using initializer lists with curly braces and pairs inside curly braces.

2. Step 2: Identify correct syntax

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; uses double braces with pairs correctly. Options A, B, and C use invalid syntax for map initialization.

3. Final Answer:

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; -> Option A

4. Quick Check:

   Correct map initialization syntax [OK]

Hint: Use double braces with pairs for map initialization [OK]

Common Mistakes:

• Using colon instead of comma in initializer list
• Using parentheses instead of braces for pairs
• Using square brackets for initialization

3. What is the output of the following C++ code snippet?

std::string s = "MCMXCIV";
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for (int i = 0; i < s.size(); ++i) {
  if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
    result -= roman[s[i]];
  } else {
    result += roman[s[i]];
  }
}
std::cout << result << std::endl;

medium

A. 1904

B. 1994

C. 1094

D. 1949

Solution

1. Step 1: Trace the loop through the string "MCMXCIV"

   Check each character and compare with next: M(1000), C(100), M(1000), X(10), C(100), I(1), V(5). Subtract when current < next, else add.

2. Step 2: Calculate result step-by-step

   Positions: M(1000, add), C(100, next M=1000 > 100 subtract), M(1000, add), X(10, next C=100 > 10 subtract), C(100, add), I(1, next V=5 > 1 subtract), V(5, add). Calculation: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   Roman "MCMXCIV" = 1994 [OK]

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

Common Mistakes:

• Adding all values without subtraction
• Misreading character values
• Off-by-one errors in loop

4. Identify the bug in the following C++ code for Roman to Integer conversion:

int romanToInt(std::string s) {
  std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
  int result = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (roman[s[i]] < roman[s[i+1]]) {
      result -= roman[s[i]];
    } else {
      result += roman[s[i]];
    }
  }
  return result;
}

medium

A. Accessing s[i+1] without checking bounds causes out-of-range error

B. Using map instead of unordered_map causes slow lookup

C. Result variable should be initialized to 1 instead of 0

D. The subtraction logic is reversed

Solution

1. Step 1: Analyze loop and index usage

   The loop runs from i = 0 to s.size() - 1, but inside the loop it accesses s[i+1] without checking if i+1 is within bounds.

2. Step 2: Identify potential runtime error

   When i is the last index, s[i+1] is out of range, causing undefined behavior or crash.

3. Final Answer:

   Accessing s[i+1] without checking bounds causes out-of-range error -> Option A

4. Quick Check:

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

Hint: Always check index bounds before accessing next element [OK]

Common Mistakes:

• Ignoring index bounds causing runtime errors
• Incorrect initialization of result
• Misunderstanding subtraction logic

5. Given the Roman numeral string "XLIX", which of the following C++ code snippets correctly converts it to an integer?

hard

A. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
total += roman[s[i]];
}
return total;
}

B. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (roman[s[i]] > roman[s[i+1]]) {
total += roman[s[i]];
} else {
total -= roman[s[i]];
}
}
return total;
}

C. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

D. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

Solution

1. Step 1: Check correct subtraction logic with bounds check

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } correctly checks if next character exists and if current value is less than next, then subtracts; else adds.

2. Step 2: Verify other options for errors

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (roman[s[i]] > roman[s[i+1]]) { total += roman[s[i]]; } else { total -= roman[s[i]]; } } return total; } reverses logic and lacks bounds check; int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = s.size() - 1; i >= 0; --i) { if (roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } accesses s[i+1] when i is last index (out-of-bounds); int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { total += roman[s[i]]; } return total; } adds all values ignoring subtraction rule.

3. Final Answer:

   The code in Step 1 -> Option D

4. Quick Check:

   Check bounds and subtract if current < next [OK]

Hint: Check next char exists before subtracting current [OK]

Common Mistakes:

• Not checking index bounds before accessing s[i+1]
• Reversing subtraction logic
• Ignoring subtraction rule completely