Roman to Integer Conversion in DSA Java - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total = 0

↓

Read current Roman symbol

↓

Compare current symbol value with next symbol value

↓

Next symbol smaller or equal?

↓

Add current symbol value to total

↓

Move to next symbol

↓

Repeat until end

No↓

Subtract current symbol value from total

↓

Move to next symbol

↓

Repeat until end

↓

Return total

We read each Roman symbol left to right, add or subtract its value based on the next symbol, and accumulate the total.

Execution Sample

DSA Java

int romanToInt(String s) {
  int total = 0;
  for (int i = 0; i < s.length(); i++) {
    int value = valueOf(s.charAt(i));
    if (i + 1 < s.length() && value < valueOf(s.charAt(i + 1))) {
      total -= value;
    } else {
      total += value;
    }
  }
  return total;
}

Converts a Roman numeral string to an integer by adding or subtracting symbol values.

Execution Table

Step	Operation	Current Symbol	Next Symbol	Compare Values	Add or Subtract	Total After Operation
1	Read symbol	M	C	1000 >= 100	Add 1000	1000
2	Read symbol	C	M	100 < 1000	Subtract 100	900
3	Read symbol	M	X	1000 >= 10	Add 1000	1900
4	Read symbol	X	C	10 < 100	Subtract 10	1890
5	Read symbol	C	I	100 >= 1	Add 100	1990
6	Read symbol	I	V	1 < 5	Subtract 1	1989
7	Read symbol	V	null	5 >= null	Add 5	1994
8	End	null	null	End of string	Return total	1994

💡 Reached end of string, total is final integer value.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
total	0	1000	900	1900	1890	1990	1989	1994	1994
i	0	1	2	3	4	5	6	7	7
current symbol	null	M	C	M	X	C	I	V	null
next symbol	null	C	M	X	C	I	V	null	null

Key Moments - 3 Insights

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

Because in Roman numerals, a smaller value before a larger value means subtraction. See steps 2 and 4 in the execution_table where subtraction happens.

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. Step 7 shows adding the last symbol 'V'.

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

Because some Roman numerals use subtractive notation (like IV for 4). Comparing lets us decide whether to add or subtract. This is shown in the compare values column in the execution_table.

Visual Quiz - 3 Questions

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

A 900

B 1900

C 1890

D 1000

💡 Hint

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

At which step does the algorithm subtract the value of the current symbol?

A Step 1

B Step 3

C Step 2

D Step 7

💡 Hint

Look for 'Subtract' in the 'Add or Subtract' column in the execution_table.

If the input was 'III', how would the total change after the second symbol?

A It would be 2

B It would be 3

C It would be 1

D It would be 0

💡 Hint

Each 'I' is 1 and since next symbol is not larger, we add. Check variable_tracker for total changes.

Concept Snapshot

Roman to Integer Conversion:
- Read symbols left to right
- If current < next, subtract current
- Else, add current
- Sum all for final integer
- Handles subtractive notation like IV=4

Full Transcript

This visual trace shows how to convert a Roman numeral string to an integer. We start with total zero and read each symbol from left to right. For each symbol, we compare its value to the next symbol's value. If the current symbol is smaller, we subtract its value from the total. Otherwise, we add it. This handles special cases like IV where I is before V and means 4. The execution table shows each step with the current and next symbols, the comparison, and the running total. The variable tracker shows how total and index change after each step. Key moments clarify why subtraction happens and what to do at the last symbol. The quiz tests understanding of the total at specific steps and the subtraction logic. This method correctly converts Roman numerals to integers by following these simple rules.

Practice

1. What is the value of the Roman numeral IX when converted to an integer?

easy

A. 6

B. 11

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 1 is subtracted 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
• Confusing IX with XI
• Ignoring subtraction rule

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

easy

A. Map map = new HashMap<>(); map.add('I', 1); map.add('V', 5);

B. Map map = Map.of("I", 1, "V", 5, "X", 10);

C. Map map = new Map(); map['I'] = 1; map['V'] = 5;

D. Map map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10);

Solution

1. Step 1: Check correct Map initialization syntax in Java

   Java requires using a concrete class like HashMap to create a Map instance. Then, use put() method to add key-value pairs.

2. Step 2: Verify each option

   Map map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); correctly uses new HashMap<>(), then map.put() calls. B uses Map.of with string keys ("I", etc.) causing type mismatch for Map<Character, Integer>. Options C and D use invalid syntax.

3. Final Answer:

   Map map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); -> Option D

4. Quick Check:

   Use HashMap and put() for map initialization [OK]

Hint: Use HashMap and put() to add entries [OK]

Common Mistakes:

• Using invalid Map constructor
• Using map.add() instead of map.put()
• Trying to assign values with brackets

3. What is the output of the following Java code snippet?

String s = "MCMXCIV";
int result = 0;
Map map = Map.of('I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000);
for (int i = 0; i < s.length(); i++) {
    int value = map.get(s.charAt(i));
    if (i + 1 < s.length() && value < map.get(s.charAt(i + 1))) {
        result -= value;
    } else {
        result += value;
    }
}
System.out.println(result);

medium

A. 1904

B. 1994

C. 1094

D. 1949

Solution

1. Step 1: Understand the Roman numeral string and map values

   The string "MCMXCIV" represents a Roman numeral. Map assigns values: M=1000, C=100, X=10, I=1, V=5.

2. Step 2: Trace the loop and calculate result

   Loop through each character:
   - M(1000), next C(100): 1000 > 100, add 1000
   - C(100), next M(1000): 100 < 1000, subtract 100
   - M(1000), next X(10): 1000 > 10, add 1000
   - X(10), next C(100): 10 < 100, subtract 10
   - C(100), next I(1): 100 > 1, add 100
   - I(1), next V(5): 1 < 5, subtract 1
   - V(5), no next, add 5
   Sum = 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   MCMXCIV = 1994 [OK]

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

Common Mistakes:

• Adding all values without subtraction
• Incorrectly subtracting when not needed
• Misreading character order

4. The following Java method aims to convert a Roman numeral string to an integer but has a bug. What is the bug?

public int romanToInt(String s) {
    Map map = Map.of('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++) {
        int value = map.get(s.charAt(i));
        if (i + 1 < s.length() && value > map.get(s.charAt(i + 1))) {
            result -= value;
        } else {
            result += value;
        }
    }
    return result;
}

medium

A. The comparison operator should be '<' instead of '>' in the if condition.

B. The map initialization is incorrect and causes runtime error.

C. The loop should start from 1 instead of 0.

D. The method does not handle lowercase Roman numerals.

Solution

1. Step 1: Analyze the if condition logic

   The code subtracts value when current value is greater than next. But Roman numerals subtract when current is less than next.

2. Step 2: Identify the correct comparison operator

   The condition should be value < map.get(next char) to subtract, not value > next value.

3. Final Answer:

   The comparison operator should be '<' instead of '>' in the if condition. -> Option A

4. Quick Check:

   Subtract when current < next [OK]

Hint: Subtract if current numeral is smaller than next [OK]

Common Mistakes:

• Using wrong comparison operator
• Ignoring subtraction rule
• Assuming map initialization error

5. You want to convert a list of Roman numerals ["XL", "IX", "MMXX"] to their integer values using Java. Which approach correctly handles this with minimal code duplication?

hard

A. Write a separate method to convert one Roman numeral to integer, then loop over the list calling this method for each element.

B. Manually convert each Roman numeral in the list with separate code blocks for each string.

C. Use a single loop over the list and convert each character individually without a helper method.

D. Convert only the first Roman numeral and reuse the result for all elements.

Solution

1. Step 1: Identify the need for reusable code

   Converting Roman numerals requires the same logic for each string. Writing a helper method avoids repeating code.

2. Step 2: Use a loop to process the list

   Loop through the list and call the helper method for each Roman numeral string to get its integer value.

3. Final Answer:

   Write a separate method to convert one Roman numeral to integer, then loop over the list calling this method for each element. -> Option A

4. Quick Check:

   Use helper method + loop for clean code [OK]

Hint: Use helper method and loop to avoid repetition [OK]

Common Mistakes:

• Repeating conversion code for each string
• Ignoring code reuse principles
• Using incorrect logic for all elements