Roman to Integer Conversion in DSA C++ - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total = 0

↓

Read next Roman symbol

↓

Compare current symbol value with next symbol value

↓

Subtract current

↓

Move to next symbol

↓

Repeat until end

↓

Return total

We read each Roman symbol, compare it with the next one, subtract if smaller, else add, and move forward until all symbols are processed.

Execution Sample

DSA C++

int romanToInt(string s) {
  auto val = [&](char c) -> int {
    switch(c) {
      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 total = 0;
  for (int i = 0; i < s.length(); i++) {
    int value = val(s[i]);
    if (i + 1 < s.length() && value < val(s[i+1]))
      total -= value;
    else
      total += value;
  }
  return total;
}

This code converts a Roman numeral string to an integer by adding or subtracting symbol values based on the next symbol.

Execution Table

Step	Current Symbol	Next Symbol	Current Value	Next Value	Condition (Current < Next)	Action	Total After Step	Visual State
1	M	C	1000	100	No	Add 1000	1000	M(1000)
2	C	M	100	1000	Yes	Subtract 100	900	M(1000) -> C(-100)
3	M	X	1000	10	No	Add 1000	1900	M(1000) -> C(-100) -> M(1000)
4	X	I	10	1	No	Add 10	1910	M(1000) -> C(-100) -> M(1000) -> X(10)
5	I	V	1	5	Yes	Subtract 1	1909	M(1000) -> C(-100) -> M(1000) -> X(10) -> I(-1)
6	V	null	5	0	No	Add 5	1914	M(1000) -> C(-100) -> M(1000) -> X(10) -> I(-1) -> V(5)
7	End	End	0	0	N/A	Return total	1914	Final total = 1914

💡 Reached end of string, total computed as 1914

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
total	0	1000	900	1900	1910	1909	1914	1914
i	0	1	2	3	4	5	6	6
current_symbol	null	M	C	M	X	I	V	End
next_symbol	null	C	M	X	I	V	null	End

Key Moments - 3 Insights

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

Because in Roman numerals, a smaller symbol before a larger one means subtraction. For example, in step 2, 'C' (100) is before 'M' (1000), so we subtract 100 as shown in execution_table row 2.

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

We always add the last symbol's value because there is no next symbol to compare. In step 6, 'V' is last, so we add 5 as shown in execution_table row 6.

Why do we compare current symbol with next symbol instead of just adding all values?

Because some Roman numerals use subtraction notation. Without comparing, 'IV' would be 1+5=6 instead of 4. The comparison ensures correct addition or subtraction, as seen in steps 5 and 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total after processing the third symbol?

A 1000

B 900

C 1900

D 1910

💡 Hint

Check the 'Total After Step' column at step 3 in the execution_table.

At which step does the condition 'Current < Next' become true for the first time?

A Step 2

B Step 1

C Step 4

D Step 5

💡 Hint

Look at the 'Condition (Current < Next)' column in the execution_table.

If the input was 'III' instead of 'MCMXCIV', how would the total change after step 3?

A It would be 1

B It would be 3

C It would be 2

D It would be 0

💡 Hint

Consider that all symbols 'I' are added because none are less than the next.

Concept Snapshot

Roman to Integer Conversion:
- Read each symbol left to right
- Compare current symbol value with next
- If current < next, subtract current
- Else, add current
- Sum all to get integer value
- Handles subtractive notation like IV=4

Full Transcript

This visualization shows how to convert Roman numerals to integers by reading each symbol, comparing it with the next, and deciding to add or subtract its value. We start with total zero, then for each symbol, if its value is less than the next symbol's value, we subtract it; otherwise, we add it. This handles special cases like IV (4) where I is less than V. The example input 'MCMXIV' is processed step-by-step, updating the total accordingly until the entire string is converted to 1914.

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