Roman to Integer Conversion in DSA C - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with input Roman string

↓

Initialize total = 0, index = 0

↓

Check current and next Roman chars

↓

If current < next: subtract current value

↓

Else: add current value

↓

Move index forward by 1

↓

Repeat until end of string

↓

Return total as integer

We scan the Roman numeral string from left to right, adding or subtracting values based on the order of symbols, until the entire string is processed.

Execution Sample

DSA C

int value(char c) {
  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 romanToInt(char *s) {
  int total = 0, i = 0;
  while (s[i]) {
    int curr = value(s[i]);
    int next = value(s[i+1]);
    if (curr < next) total -= curr;
    else total += curr;
    i++;
  }
  return total;
}

This code converts a Roman numeral string to an integer by adding or subtracting symbol values while scanning the string.

Execution Table

Step	Operation	Current Char	Next Char	Add or Subtract	Total After Operation	Visual State
1	Read chars	M	C	Add 1000	1000	M(1000)
2	Read chars	C	M	Subtract 100	900	M(1000) - C(100)
3	Read chars	M	X	Add 1000	1900	M(1000) - C(100) + M(1000)
4	Read chars	X	I	Add 10	1910	M(1000) - C(100) + M(1000) + X(10)
5	Read chars	I	V	Subtract 1	1909	M(1000) - C(100) + M(1000) + X(10) - I(1)
6	Read chars	V		Add 5	1914	M(1000) - C(100) + M(1000) + X(10) - I(1) + V(5)
7	End of string			Stop	1914	Final total = 1914

💡 Reached end of string, no more characters to process.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
i (index)	0	1	2	3	4	5	6	6
total	0	1000	900	1900	1910	1909	1914	1914
curr (value)	-	1000	100	1000	10	1	5	-
next (value)	-	100	1000	10	1	5	0	-

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 value before a larger one means subtraction. For example, in step 2, 'C' (100) is before 'M' (1000), so we subtract 100 instead of adding it.

Why do we add the current value when it is greater or equal to the next value?

When the current Roman numeral is equal or larger than the next, it means normal addition. For example, in step 1, 'M' (1000) is before 'C' (100), so we add 1000.

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

We always add the value of the last character because there is no next character to compare. In step 6, 'V' (5) is the last character, so we add 5.

Visual Quiz - 3 Questions

Look at the execution table, what is the total after step 3?

A 1000

B 900

C 1900

D 1910

💡 Hint

Check the 'Total After Operation' column in row for step 3.

At which step does the algorithm subtract a value?

A Step 1

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Add or Subtract' column for the word 'Subtract'.

If the input was 'III', how would the total change after step 2 compared to the current example?

A It would be 2

B It would be 3

C It would be 1

D It would be 0

💡 Hint

Consider that 'I' is 1 and no subtraction occurs in 'III'.

Concept Snapshot

Roman to Integer Conversion:
- Scan Roman string left to right
- Map each symbol to its value
- If current < next, subtract current
- Else, add current
- Continue until end
- Return total integer value

Full Transcript

This concept converts Roman numerals to integers by scanning the string from left to right. At each step, it compares the current Roman symbol's value with the next one. If the current value is less than the next, it subtracts it from the total; otherwise, it adds it. This process continues until the entire string is processed, resulting in the integer equivalent of the Roman numeral.

Practice

1. What is the main rule to convert Roman numerals to integers?
Example: IV = 4, VI = 6

easy

A. Multiply values of all symbols

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

C. Add values only if symbols are in alphabetical order

D. Subtract values of all symbols

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals add values of symbols, but if a smaller symbol appears before a larger one, it is subtracted.

2. Step 2: Apply rule to example

   For IV, I (1) is before V (5), so subtract 1 from 5 = 4. For VI, V (5) before I (1), so add 5 + 1 = 6.

3. Final Answer:

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

4. Quick Check:

   IV = 4, VI = 6 [OK]

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

Common Mistakes:

• Always adding without subtraction
• Multiplying symbols instead of adding
• Ignoring order of symbols

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

easy

A. int values = {'I':1, 'V':5, 'X':10};

B. int values[] = {I=1, V=5, X=10};

C. int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10};

D. int values[3] = {1, 5, 10};

Solution

1. Step 1: Understand C array initialization for character keys

   In C, to map characters to values, an array indexed by character offset is used, e.g., values['I'-'A'] = 1.

2. Step 2: Check each option

   int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10}; uses correct syntax for sparse initialization. Options B and C use invalid syntax for C. int values[3] = {1, 5, 10}; initializes array without mapping to characters.

3. Final Answer:

   int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10}; -> Option C

4. Quick Check:

   Correct C syntax for char-indexed array [OK]

Hint: Use array with char offset for mapping in C [OK]

Common Mistakes:

• Using dictionary syntax not valid in C
• Not indexing array by character offset
• Initializing array without specifying indices

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

char *s = "MCMXCIV";
int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50, ['C'-'A']=100, ['D'-'A']=500, ['M'-'A']=1000};
int result = 0, i = 0;
while (s[i]) {
  int curr = values[s[i]-'A'];
  int next = values[s[i+1]-'A'];
  if (next > curr) result -= curr;
  else result += curr;
  i++;
}
printf("%d", result);

medium

A. Error

B. 1904

C. 1494

D. 1994

Solution

1. Step 1: Trace each character and apply addition/subtraction

   String: M(1000), C(100), M(1000), X(10), C(100), I(1), V(5). Check pairs:
   M(1000) next C(100) -> 100 < 1000? No, add 1000
   C(100) next M(1000) -> 1000 > 100, subtract 100
   M(1000) next X(10) -> 10 < 1000, add 1000
   X(10) next C(100) -> 100 > 10, subtract 10
   C(100) next I(1) -> 1 < 100, add 100
   I(1) next V(5) -> 5 > 1, subtract 1
   V(5) next 0, add 5

2. Step 2: Calculate total

   1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

3. Final Answer:

   1994 -> Option D

4. Quick Check:

   MCMXCIV = 1994 [OK]

Hint: Subtract when next symbol is larger [OK]

Common Mistakes:

• Adding all values without subtraction
• Off-by-one error accessing next character
• Incorrect mapping of Roman symbols

4. Find the bug in this C code for Roman to Integer conversion:

int romanToInt(char *s) {
  int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50, ['C'-'A']=100, ['D'-'A']=500, ['M'-'A']=1000};
  int result = 0, i = 0;
  while (s[i]) {
    int curr = values[s[i]-'A'];
    int next = values[s[i+1]-'A'];
    if (curr < next) result += curr;
    else result -= curr;
    i++;
  }
  return result;
}

medium

A. The addition and subtraction logic is reversed

B. Array indexing causes out-of-bounds error

C. Values array is not initialized correctly

D. Function does not handle empty string

Solution

1. Step 1: Analyze addition and subtraction conditions

   Code adds current value if curr < next, else subtracts. This is opposite of Roman rules where smaller before larger means subtract.

2. Step 2: Correct logic

   It should subtract curr if curr < next, else add curr.

3. Final Answer:

   The addition and subtraction logic is reversed -> Option A

4. Quick Check:

   Subtract when smaller before larger [OK]

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

Common Mistakes:

• Swapping add and subtract conditions
• Ignoring last character's next value
• Not initializing values array properly

5. Given the Roman numeral string "XLIX", which of the following C functions correctly returns its integer value?

hard

A. int romanToInt(char *s) { int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50}; int res=0,i=0; while(s[i]) { int curr=values[s[i]-'A'], next=values[s[i+1]-'A']; if(curr

B. int romanToInt(char *s) { int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50}; int res=0,i=0; while(s[i]) { int curr=values[s[i]-'A'], next=values[s[i+1]-'A']; if(curr>next) res-=curr; else res+=curr; i++; } return res; }

C. int romanToInt(char *s) { int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50}; int res=0,i=0; while(s[i]) { int curr=values[s[i]-'A']; res+=curr; i++; } return res; }

D. int romanToInt(char *s) { int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50}; int res=0,i=0; while(s[i]) { int curr=values[s[i]-'A'], next=values[s[i+1]-'A']; if(curr<=next) res-=curr; else res+=curr; i++; } return res; }

Solution

1. Step 1: Check logic for subtraction and addition

   int romanToInt(char *s) { int values[26] = {['I'-'A']=1, ['V'-'A']=5, ['X'-'A']=10, ['L'-'A']=50}; int res=0,i=0; while(s[i]) { int curr=values[s[i]-'A'], next=values[s[i+1]-'A']; if(curr

2. Step 2: Verify with example "XLIX"

   X(10) < L(50) subtract 10
   L(50) > I(1) add 50
   I(1) < X(10) subtract 1
   X(10) no next add 10
   Total = -10 + 50 - 1 + 10 = 49

3. Final Answer:

   Option A correctly returns 49 for "XLIX" -> Option A

4. Quick Check:

   Subtract if smaller before larger [OK]

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

Common Mistakes:

• Using <= instead of < for subtraction
• Adding all values without subtraction
• Incorrect comparison operators