romanflow.md

Roman to Integer Conversion Flow

This document explains the romanToInt function, which converts a Roman numeral string to its integer equivalent. The function is implemented in JavaScript and handles standard Roman numeral rules, including subtractive cases (e.g., IV = 4). Below, we provide a Mermaid flowchart to visualize the algorithm's flow and a step-by-step example for the input "XIV".

Function Overview

The romanToInt function takes a string s of Roman numerals and returns the corresponding integer. It uses a dictionary to map Roman symbols to their values and processes the string from left to right, handling subtractive cases by checking if the next symbol has a greater value.

Code

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const roman = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let runningTotal = 0;

    for (let i = 0; i < s.length; i++) {
        const key = s[i];
        const currentValue = roman[key];

        if (i < s.length - 1 && roman[s[i + 1]] > currentValue) {
            runningTotal -= currentValue;
        } else {
            runningTotal += currentValue;
        }
    }

    return runningTotal;
};

Flowchart

The following Mermaid flowchart illustrates the algorithm's logic:

graph TD
    A[Start] --> B[Initialize roman dictionary: <br> I=1, V=5, X=10, L=50, C=100, D=500, M=1000]
    B --> C[Set runningTotal = 0]
    C --> D[Set i = 0]
    D --> E{i < s.length?}
    E -->|Yes| F["Get key = s[i]"]
    F --> G["Get currentValue = roman[key]"]
    G --> H{i < s.length - 1?}
    H -->|Yes| I["Is roman[s[i + 1]] > currentValue?"]
    I -->|Yes| J[runningTotal -= currentValue]
    I -->|No| K[runningTotal += currentValue]
    H -->|No| K
    J --> L[Increment i]
    K --> L
    L --> E
    E -->|No| M[Return runningTotal]
    M --> N[End]

Loading

Step-by-Step Example: Input "XIV"

Let’s walk through how the function processes the input "XIV" (Roman numeral for 14).

Setup

• Input: s = "XIV"
• Dictionary: roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
• Initial State: runningTotal = 0, i = 0

Steps

1. i = 0:

   • key = s[0] = 'X'
   • currentValue = roman['X'] = 10
   • Check: i < s.length - 1 (0 < 3 - 1 = 2) is true
   • Compare: roman[s[1]] = roman['I'] = 1, 1 > 10 is false
   • Action: runningTotal += 10 → runningTotal = 10
   • Increment: i = 1

2. i = 1:

   • key = s[1] = 'I'
   • currentValue = roman['I'] = 1
   • Check: i < s.length - 1 (1 < 2) is true
   • Compare: roman[s[2]] = roman['V'] = 5, 5 > 1 is true
   • Action: runningTotal -= 1 → runningTotal = 10 - 1 = 9
   • Increment: i = 2

3. i = 2:

   • key = s[2] = 'V'
   • currentValue = roman['V'] = 5
   • Check: i < s.length - 1 (2 < 2) is false
   • Action: runningTotal += 5 → runningTotal = 9 + 5 = 14
   • Increment: i = 3

4. Loop Exit:

   • i = 3, i < s.length (3 < 3) is false
   • Return: runningTotal = 14

Result

• Output: 14 (X = 10, IV = 4, total = 10 + 4 = 14)

Explanation of Logic

• The function iterates through each character in the input string.
• For each character, it retrieves its value from the roman dictionary.
• If the next character exists and has a greater value (e.g., I before V in IV), the current value is subtracted (handling cases like IV = 5 - 1 = 4).
• Otherwise, the current value is added (e.g., X in XIV).
• This ensures correct handling of both additive (e.g., VI = 5 + 1 = 6) and subtractive (e.g., IV) cases.

Notes

• Input Constraints: The input s is assumed to be a valid Roman numeral string (1 to 3999).
• Edge Cases:
  • Single character: "V" → 5
  • Subtractive cases: "IV" → 4, "CM" → 900
  • Repeated symbols: "III" → 3
• Performance: O(n) time complexity, where n is the length of the input string.