Roman to Integer Problem and Solution

1. Introduction

The "Roman to Integer" problem is the inverse of converting an integer to a Roman numeral. It involves translating a Roman numeral string back into an integer. Roman numerals are composed of letters representing values, and the goal is to sum these values, accounting for subtractive notation.

2. Problem

Given a Roman numeral, convert it to an integer. Roman numerals are represented by combinations of letters from the Latin alphabet: I, V, X, L, C, D, and M.

2. Solution in C++

#include <iostream>
#include <unordered_map>
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 sum = 0;
    for (int i = 0; i < s.length(); i++) {
        if (i < s.length() - 1 && roman[s[i]] < roman[s[i + 1]]) {
            sum -= roman[s[i]];
        } else {
            sum += roman[s[i]];
        }
    }
    return sum;
}

// Example usage
int main() {
    string roman = "LVIII";
    cout << "Integer: " << romanToInt(roman) << endl;
    return 0;
}

Output:

Integer: 58

Explanation:

1. romanToInt in C++ uses a hashmap to map Roman numerals to their values.

2. It iterates over the string, adding the values of the numerals.

3. If a smaller numeral precedes a larger one, it subtracts that numeral's value (subtractive notation).

4. The final sum represents the integer value of the Roman numeral.

3. Solution in Java

public class RomanToInteger {
    public static int romanToInt(String s) {
        int[] roman = new int[128];
        roman['I'] = 1; roman['V'] = 5; roman['X'] = 10;
        roman['L'] = 50; roman['C'] = 100; roman['D'] = 500; roman['M'] = 1000;

        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i < s.length() - 1 && roman[s.charAt(i)] < roman[s.charAt(i + 1)]) {
                sum -= roman[s.charAt(i)];
            } else {
                sum += roman[s.charAt(i)];
            }
        }
        return sum;
    }

    // Example usage
    public static void main(String[] args) {
        String roman = "LVIII";
        System.out.println("Integer: " + romanToInt(roman));
    }
}

Output:

Integer: 58

Explanation:

1. Java's romanToInt uses an array for the Roman numeral mapping.

2. Iterates through the string, adding the numeral values.

3. Subtracts the value of smaller numerals preceding larger ones.

4. Returns the total sum as the integer value.

4. Solution in Python

def roman_to_int(s):
    roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    sum = 0
    for i in range(len(s)):
        if i < len(s) - 1 and roman[s[i]] < roman[s[i + 1]]:
            sum -= roman[s[i]]
        else:
            sum += roman[s[i]]
    return sum

# Example usage
roman = "LVIII"
print("Integer:", roman_to_int(roman))

Output:

Integer: 58

Explanation:

1. Python's roman_to_int uses a dictionary for the Roman numeral values.

2. The function sums the values, using subtraction for smaller values before larger ones.

3. Returns the summed value, representing the integer equivalent.