Roman to Integer Conversion in DSA Rust - Execution Trace

Concept Flow - Roman to Integer Conversion

Start with total = 0

↓

Read next Roman symbol

↓

Check if current symbol < next symbol?

↓

Subtract current

↓

Move to next symbol

↓

More symbols?

↓

Repeat

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 Rust

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let values = [('I',1), ('V',5), ('X',10), ('L',50), ('C',100), ('D',500), ('M',1000)];
    // logic to convert
}

This function converts a Roman numeral string to an integer by processing each symbol.

Execution Table

Step	Operation	Current Symbol	Next Symbol	Add or Subtract	Total After Operation	Visual State
1	Read symbol	X	I	Add 10	10	X(10)
2	Read symbol	I	V	Subtract 1	9	X(10) -> I(-1)
3	Read symbol	V	None	Add 5	14	X(10) -> I(-1) -> V(5)
4	End	None	None	Return total	14	Final total = 14

💡 All symbols processed, total computed as 14

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
total	0	10	9	14	14
current_symbol	None	X	I	V	None
next_symbol	None	I	V	None	None

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, as shown in step 2 where 'I' before 'V' subtracts 1 (execution_table row 2).

What happens when we reach the last symbol?

We add its value directly since there is no next symbol to compare, as in step 3 with 'V' (execution_table row 3).

Why do we keep track of the next symbol?

To decide whether to add or subtract the current symbol's value, as the decision depends on comparing current and next symbols (concept_flow and execution_table rows 1-3).

Visual Quiz - 3 Questions

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

A 10

B 14

C 9

D 1

💡 Hint

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

At which step does the algorithm subtract a value?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Add or Subtract' column in the execution_table to find where subtraction occurs.

If the input was 'XI' instead of 'XIV', what would be the total after the first symbol?

A 1

B 10

C 9

D 0

💡 Hint

Refer to the variable_tracker and concept_flow to see how the first symbol's value is handled.

Concept Snapshot

Roman to Integer Conversion:
- Read symbols left to right
- If current < next, subtract current
- Else, add current
- Sum all for final integer
- Use map for symbol values

Full Transcript

This visual execution trace shows how to convert Roman numerals to integers. We start with total zero and read each symbol from left to right. For each symbol, we compare it with the next one. If the current symbol is smaller, we subtract its value; otherwise, we add it. We update the total accordingly. This process continues until all symbols are processed. The example 'XIV' is traced step-by-step, showing how the total changes from 0 to 14. Key points include why subtraction happens and how the last symbol is handled. The variable tracker shows the values of total, current symbol, and next symbol at each step. The quiz tests understanding of these steps.

Practice

1. What is the main rule to convert Roman numerals to integers?

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 the same

D. Subtract values of all symbols

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals are added normally, but if a smaller numeral appears before a larger one, it is subtracted.

2. Step 2: Apply the rule to conversion

   When converting, add each symbol's value unless a smaller symbol precedes a larger one, then subtract the smaller.

3. Final Answer:

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

4. Quick Check:

   Roman to integer = add or subtract based on order [OK]

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

Common Mistakes:

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

2. Which Rust code snippet correctly defines a function header for converting a Roman numeral string to an integer?

easy

A. fn roman_to_int(s: &str) -> i32 {

B. fn romanToInt(s: String) -> int {

C. function roman_to_int(s: &str) -> i32 {

D. fn roman_to_int(s: &String) -> i64 {

Solution

1. Step 1: Check Rust function syntax

   Rust functions start with fn, use snake_case, and specify parameter types and return type correctly.

2. Step 2: Validate each option

   fn roman_to_int(s: &str) -> i32 { uses correct Rust syntax: fn, snake_case, &str parameter, and i32 return type. Others have syntax errors or wrong types.

3. Final Answer:

   fn roman_to_int(s: &str) -> i32 { -> Option A

4. Quick Check:

   Rust fn header with &str and i32 return [OK]

Hint: Use fn, snake_case, &str param, i32 return [OK]

Common Mistakes:

• Using camelCase instead of snake_case
• Wrong parameter or return types
• Using 'function' keyword (not Rust)

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

fn main() {
    let s = "IX";
    let result = roman_to_int(s);
    println!("{}", result);
}

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars().rev() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            _ => 0,
        };
        if value < prev {
            total -= value;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

medium

A. 6

B. 11

C. Error

D. 9

Solution

1. Step 1: Trace characters in reverse

   Input "IX" reversed is 'X' then 'I'. 'X' = 10, 'I' = 1.

2. Step 2: Calculate total with subtraction rule

   Start total=0, prev=0. 'X' (10) >= prev(0), total=10, prev=10. Next 'I' (1) < prev(10), total=10-1=9, prev=1.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   "IX" = 9 [OK]

Hint: Traverse string backward, subtract if smaller before larger [OK]

Common Mistakes:

• Not reversing string for correct subtraction
• Adding all values without subtraction
• Misassigning values to characters

4. Identify the bug in this Rust function for Roman to integer conversion:

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            _ => 0,
        };
        if value > prev {
            total += value - 2 * prev;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

medium

A. Loop should iterate in reverse order

B. Subtracting twice prev is incorrect

C. Match arms missing some Roman numerals

D. prev variable should be mutable

Solution

1. Step 1: Inspect the match expression

   The match only handles 'I'(1), 'V'(5), 'X'(10). It misses 'L'(50), 'C'(100), 'D'(500), 'M'(1000), causing other symbols to map to 0 and produce wrong results.

2. Step 2: Verify other options

   A: Forward iteration with 'value - 2*prev' is valid for handling subtractive notation. B: The 2*prev subtraction corrects the previously added prev value. D: 'prev' is already mutable.

3. Final Answer:

   Match arms missing some Roman numerals -> Option C

4. Quick Check:

   Match must cover I,V,X,L,C,D,M [OK]

Hint: Include match arms for all Roman numerals [OK]

Common Mistakes:

• Incomplete match arms
• Not handling all Roman numerals
• Forgetting to make prev mutable (already mutable here)

5. Given the Roman numeral string "MCMXCIV", what integer does the following Rust function return?

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars().rev() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            'L' => 50,
            'C' => 100,
            'D' => 500,
            'M' => 1000,
            _ => 0,
        };
        if value < prev {
            total -= value;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

hard

A. 1994

B. 1904

C. 2004

D. None of the above

Solution

1. Step 1: Reverse and assign values

   Reverse "MCMXCIV" to "VICXMCM". Values: V=5, I=1, C=100, X=10, M=1000, C=100, M=1000.

2. Step 2: Calculate total with subtraction rule

   Start total=0, prev=0. - V(5) >= prev(0): total=5, prev=5 - I(1) < prev(5): total=5-1=4, prev=1 - C(100) >= prev(1): total=4+100=104, prev=100 - X(10) < prev(100): total=104-10=94, prev=10 - M(1000) >= prev(10): total=94+1000=1094, prev=1000 - C(100) < prev(1000): total=1094-100=994, prev=100 - M(1000) >= prev(100): total=994+1000=1994, prev=1000

3. Final Answer:

   1994 -> Option A

4. Quick Check:

   "MCMXCIV" = 1994 [OK]

Hint: Reverse string, subtract if smaller before larger [OK]

Common Mistakes:

• Not reversing string before processing
• Misassigning values to symbols
• Ignoring subtraction rule