algoadvance

Leetcode 13. Roman to Integer

Problem Statement

The task is to convert a given Roman numeral (represented as a string) to its corresponding integer value. Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M. Below is a table of these symbols with their values:

Symbol       Value
I            1
V            5
X            10
L            50
C            100
D            500
M            1000

Roman numerals are usually written from largest to smallest from left to right. However, there are exceptions where a smaller numeral precedes a larger numeral, indicating subtraction. Examples of such combinations include IV (4) and IX (9).

Clarifying Questions

  1. Input Limitations: What is the expected length or range of the input string?
  2. Input Validity: Should we assume the input is always a valid Roman numeral?
  3. Output Type: Should the function return the integer value as an integer type?

Strategy

  1. Value Mapping: Create a map to store Roman numeral characters and their corresponding integer values.
  2. Iterate and Compare: Traverse the string and for each character, compare it to the next character. If the current character is smaller than the next character, subtract its value from the total; otherwise, add its value to the total.
  3. Final Result: Return the computed total after processing all characters.

Code

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int romanToInt(string s) {
    unordered_map<char, int> roman = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000}
    };

    int total = 0;

    for (size_t i = 0; i < s.length(); ++i) {
        if (i < s.length() - 1 && roman[s[i]] < roman[s[i + 1]]) {
            total -= roman[s[i]];
        } else {
            total += roman[s[i]];
        }
    }

    return total;
}

// Test function
int main() {
    string roman = "MCMXCIV"; // 1994
    cout << "Integer value of Roman numeral " << roman << " is " << romanToInt(roman) << endl;
    return 0;
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the input string. This is because each character in the string is checked once.

Explanation

  1. Initialization: Create a map for Roman numeral values.
  2. Traversal:
    • Loop through the string.
    • Compare each character with the next one to decide whether to add or subtract its value.
  3. Calculation:
    • If the current character is less than the next, subtract its value.
    • Otherwise, add its value.
  4. Output the Result: Return the accumulated total.

This method ensures the Roman numeral string is efficiently converted to the integer value correctly based on Roman numeral rules.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI