> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/roman-to-integer.md).

# Roman to Integer

{% hint style="info" %}
Array, Iterative  Approach 
{% endhint %}

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

<pre><code><strong>Symbol       Value
</strong>I             1
V             5
X             10
L             50
C             100
D             500
M             1000
</code></pre>

For example, `2` is written as `II` in Roman numeral, just two ones added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

* `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.&#x20;
* `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.&#x20;
* `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "III"
</strong><strong>Output: 3
</strong><strong>Explanation: III = 3.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "LVIII"
</strong><strong>Output: 58
</strong><strong>Explanation: L = 50, V= 5, III = 3.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: s = "MCMXCIV"
</strong><strong>Output: 1994
</strong><strong>Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 15`
* `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
* It is **guaranteed** that `s` is a valid roman numeral in the range `[1, 3999]`.

### Solutions

The problem is to convert a Roman numeral to an integer. The solution involves a process of iterating over the Roman numeral from left to right. For each character, it adds its corresponding integer value to the result. If a character represents a value that is less than the next character’s value, it subtracts this value instead of adding it. The final result is the integer representation of the original Roman numeral.

#### Approach - Brute Force Technique

Checks each character in the string one by one.

**Steps**

1. **Dictionary Initialization**: A dictionary `romanLatters` is initialized with Roman numerals as keys and their corresponding integer values as values.
2. **Input Validation**: The `IsValidInput` function checks if the input string `s` is within the valid length (1 to 15 characters) and if all characters in `s` are valid Roman numerals. If the input string is invalid, the function returns `false`, and the `RomanToInt` function will return zero.
3. **Roman Numeral Conversion**: The `RomanToInt` function converts the input Roman numeral to an integer. It initializes an integer `output` to store the result and a variable `pre` to keep track of the value of the previous Roman numeral.
4. **Iteration Over String**: The function iterates over each character in the input string `s`. For each character, it gets the corresponding integer value `current` from the `romanLatters` dictionary.
5. **Addition and Subtraction**: If `pre` is zero or `pre` is greater than or equal to `current`, the function adds `current` to `output`. Otherwise, it subtracts `pre` from `output` and adds `current - pre` to `output`.
6. **Update Previous Value**: After processing each character, the function updates `pre` to `current`.
7. **Completion**: The function continues this process until all characters in the string have been processed. At this point, `output` is the integer equivalent of the input Roman numeral.
8. **Return Result**: Finally, the function returns the integer `output`.

```csharp
public class Solution {
    
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
         int output=0;
        if(IsValidInput(s)){
             
           
            int pre=0;
            foreach(char ch in s.ToArray()){
                
                int current=romanLatters[ch];
                if(pre==0 || pre>=current){
                   output+=current;
                }
                else {
                    output = output - pre;
                    output = output + (current-pre);
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}
```

> Complexity

* **Time Complexity:** O(1)
* **Auxiliary Space:** O(1)

**Time Complexity**: The time complexity is **O(1)**. This is because the max length of string is **15** characters.

**Space Complexity**: The space complexity is **O(1)**. The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables `output` and `pre` also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.

#### Approach - Iterative Technique

The solution involves a process of iterating over the Roman numeral from left to right. For each character, it checks if it represents a value that is less than the next character’s value. If it is, it subtracts this value from the result. Otherwise, it adds this value to the result. The final result is the integer representation of the original Roman numeral.

#### Steps

1. **Dictionary Initialization**: A dictionary `romanLatters` is initialized with Roman numerals as keys and their corresponding integer values as values.
2. **Input Validation**: The `IsValidInput` function checks if the input string `s` is within the valid length (1 to 15 characters) and if all characters in `s` are valid Roman numerals. If the input string is invalid, the function returns `false`, and the `RomanToInt` function will return zero.
3. **Roman Numeral Conversion**: The `RomanToInt` function converts the input Roman numeral to an integer. It initializes an integer `output` to store the result.
4. **Iteration Over String**: The function iterates over each character in the input string `s` using a `for` loop. For each character, it gets the corresponding integer value `current` from the `romanLatters` dictionary.
5. **Addition and Subtraction**: Inside the `for` loop, it checks if the current character’s value is less than the next character’s value. If it is, it subtracts `current` from `output`. Otherwise, it adds `current` to `output`.
6. **Completion**: The function continues this process until all characters in the string have been processed. At this point, `output` is the integer equivalent of the input Roman numeral.
7. **Return Result**: Finally, the function returns the integer `output`.

```csharp
public class Solution {
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
        int output=0;
        if(IsValidInput(s)){
             
            int pre=0;
            for(int i=0; i<s.Length; i++){
                
                int current=romanLatters[s[i]];
                if(i+1<s.Length && current<romanLatters[s[i+1]]){
                   output-=current;
                }
                else {
                    output+=current;
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}

```

> Complexity

* **Time Complexity:** O(1)
* **Auxiliary Space:** O(1)

**Time Complexity**: The time complexity is **O(1)**. This is because the max length of string is **15** characters.

**Space Complexity**: The space complexity is **O(1)**. The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables `output` and `pre` also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.