Roman to Integer Conversion in DSA Rust

Mental Model

Roman numerals are letters that represent numbers, and sometimes a smaller number before a bigger one means subtraction instead of addition.

Analogy: Think of reading a price tag where if a smaller coin is placed before a bigger coin, you subtract its value, otherwise you add it up.

R: I V X L C D M
Values: 1 5 10 50 100 500 1000
Example: M -> 1000
M -> 1000 -> C -> 100 -> M -> 1000
If smaller before bigger: subtract
Else: add

Dry Run Walkthrough

Input: Roman numeral: "MCMIV"

Goal: Convert "MCMIV" to its integer value 1904

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

Total = 1000

Why: Start with first letter 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), add 1000

Total = 900 + 1000 = 1900

Why: Add value when current is not smaller than next

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

Total = 1899 + 5 = 1904

Why: Add last value

Result:

Total = 1904

Annotated Code

DSA Rust

use std::collections::HashMap;

struct RomanConverter {
    values: HashMap<char, i32>,
}

impl RomanConverter {
    fn new() -> Self {
        let mut values = HashMap::new();
        values.insert('I', 1);
        values.insert('V', 5);
        values.insert('X', 10);
        values.insert('L', 50);
        values.insert('C', 100);
        values.insert('D', 500);
        values.insert('M', 1000);
        RomanConverter { values }
    }

    fn roman_to_int(&self, s: &str) -> i32 {
        let chars: Vec<char> = s.chars().collect();
        let mut total = 0;
        let mut i = 0;
        while i < chars.len() {
            let current_val = self.values[&chars[i]];
            if i + 1 < chars.len() && current_val < self.values[&chars[i + 1]] {
                total -= current_val;
            } else {
                total += current_val;
            }
            i += 1;
        }
        total
    }
}

fn main() {
    let converter = RomanConverter::new();
    let roman = "MCMIV";
    let result = converter.roman_to_int(roman);
    println!("{}", result);
}

while i < chars.len() {

loop through each character index

let current_val = self.values[&chars[i]];

get value of current Roman numeral

if i + 1 < chars.len() && current_val < self.values[&chars[i + 1]] {

check if next exists and current < next (subtraction case)

total -= current_val;

subtract current value for subtraction pattern

total += current_val;

add current value otherwise

i += 1;

move to next character

Output

1904

Complexity Analysis

Time: O(n) because we scan each character once

Space: O(1) because the map size is fixed and extra space is constant

vs Alternative: Compared to checking each symbol multiple times or using recursion, this linear scan is efficient and simple

Edge Cases

Empty string

Returns 0 because no numerals to convert

DSA Rust

while i < chars.len() {

Single character like 'V'

Returns value 5 correctly by adding single numeral

DSA Rust

total += current_val;

Subtraction at end like 'IV'

Correctly computes 4: subtracts 1 then adds 5

DSA Rust

if ... current_val < ... { total -= current_val }

When to Use This Pattern

When you see a problem asking to convert Roman numerals to numbers, use the subtraction detection pattern by comparing current and next symbols to decide add or subtract.

Common Mistakes

Mistake: Always adding values without checking if smaller numeral comes before bigger one
Fix: Add logic to compare current and next numeral values and subtract if current is smaller

Summary

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

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

Remember: if a smaller numeral comes before a bigger one, subtract it; otherwise, add it.

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