> 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/integer-to-roman.md).

# Integer to Roman

{% 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 one's 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 an integer, convert it to a roman numeral.

&#x20;

**Example 1:**

<pre><code><strong>Input: num = 3
</strong><strong>Output: "III"
</strong><strong>Explanation: 3 is represented as 3 ones.
</strong></code></pre>

**Example 2:**

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

**Example 3:**

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

&#x20;

**Constraints:**

* `1 <= num <= 3999`

#### Solutions

The problem is to convert an integer to a Roman numeral. The solution involves a process of repeatedly subtracting the largest possible Roman numeral value from the input number and appending the corresponding Roman numeral to the result. This process continues until the input number has been reduced to zero. The final result is the Roman numeral representation of the original input number. The solution also includes a validation step to ensure that the input number is within the valid range for Roman numerals (1 to 3999). If the input number is outside this range, the function returns an empty string.&#x20;

#### Approach - Brute Force Technique

Checks each numeral in the dictionary for every subtraction until the number becomes zero.

**Steps**

1. **Dictionary Initialization**: A dictionary `romanLatters` is initialized with integer values as keys and their corresponding Roman numerals as values. The dictionary is sorted in descending order of keys.
2. **Input Validation**: The `IsValidInput` function checks if the input number `num` is within the valid range (1 to 3999). If the input number is outside this range, the function returns `false`, and the `IntToRoman` function will return an empty string.
3. **Roman Numeral Conversion**: The `IntToRoman` function converts the input number to a Roman numeral. It initializes an empty string `result` to store the Roman numeral.
4. **Iteration Over Dictionary**: The function enters a `while` loop that continues as long as the current number `num` is not zero. Inside the `while` loop, it iterates over each item in the `romanLatters` dictionary.
5. **Subtraction and Appending**: For each dictionary item, it checks if the current number `num` is greater than or equal to the key of the item. If it is, it appends the value of the item (the Roman letter) to `result` and subtracts the key of the item (the Roman numeral) from `num`. Then it breaks the `foreach` loop and goes back to the `while` loop.
6. **Next Dictionary Item**: If `num` is not zero and is less than the key of the current dictionary item, the function moves to the next item in the dictionary and repeats the process.
7. **Completion**: The function continues this process until `num` becomes zero. At this point, all the Roman numerals that make up the input number have been appended to `result`.
8. **Return Result**: Finally, the function returns the Roman numeral as a string.

```csharp
public class Solution {
    public Dictionary<int, string> romanLatters = new Dictionary<int, string>()
    {
        {1000, "M"},
        {900, "CM"},
        {500, "D"},
        {400, "CD"},
        {100, "C"},
        {90, "XC"},
        {50, "L"},
        {40, "XL"},
        {10, "X"},
        {9, "IX"},
        {5, "V"},
        {4, "IV"},
        {1, "I"}
    };
    public string IntToRoman(int num)
    {
        if (!IsValidInput(num))
            return string.Empty;

        string result = string.Empty;
        while (num != 0)
        {

            foreach (var item in romanLatters)
            {
                if (num>=item.Key)
                {
                    result += item.Value;
                    num = num - item.Key;
                    break;

                }
            }
        }
        return result;
    }

    private bool IsValidInput(int num)
    {

        return 1 <= num && num <= 3999;
    }
}
```

> Complexity

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

**Time Complexity**: The time complexity is **O(1)**. This is because the number of Roman numerals is fixed (13 numerals), and the maximum possible number is also fixed (3999). Therefore, the number of iterations does not grow with the size of the input number, making the time complexity constant.

**Space Complexity**: The space complexity is also **O(1)**. The space used by the program does not grow with the size of the input number. The dictionary of Roman numerals uses a constant amount of space, and the string `result` will at most hold the Roman numeral equivalent of the number 3999, which is a fixed length string.

Please note that this analysis assumes that dictionary lookups, string concatenation, and integer comparisons/subtractions can be done in constant time.&#x20;

#### Approach - Iterative Technique

Iterates over the dictionary and for each key-value pair, it performs a loop operation until the number is less than the key.

**Steps**

1. **Dictionary Initialization**: A dictionary `romanLatters` is initialized with integer values as keys and their corresponding Roman numerals as values. The dictionary is sorted in descending order of keys.
2. **Input Validation**: The `IsValidInput` function checks if the input number `num` is within the valid range (1 to 3999). If the input number is outside this range, the function returns `false`, and the `IntToRoman` function will return an empty string.
3. **Roman Numeral Conversion**: The `IntToRoman` function converts the input number to a Roman numeral. It initializes an empty `StringBuilder` object `result` to store the Roman numeral.
4. **Iteration Over Dictionary**: The function iterates over each item in the `romanLatters` dictionary. For each item, it enters a `while` loop that continues as long as the current number `num` is greater than or equal to the key of the current dictionary item.
5. **Subtraction and Appending**: Inside the `while` loop, the function appends the value of the current dictionary item (the Roman letter) to `result` and subtracts the key of the current dictionary item (the Roman numeral) from `num`. This process continues until `num` becomes less than the key of the current dictionary item.
6. **Next Dictionary Item**: Once `num` becomes less than the key of the current dictionary item, the function moves to the next item in the dictionary and repeats the process.
7. **Completion**: The function continues this process until `num` becomes zero. At this point, all the Roman numerals that make up the input number have been appended to `result`.
8. **Return Result**: Finally, the function returns the Roman numeral as a string by calling the `ToString` method on `result`.

```csharp
public class Solution {
    public Dictionary<int, string> romanLatters = new Dictionary<int, string>()
    {
        {1000, "M"},
        {900, "CM"},
        {500, "D"},
        {400, "CD"},
        {100, "C"},
        {90, "XC"},
        {50, "L"},
        {40, "XL"},
        {10, "X"},
        {9, "IX"},
        {5, "V"},
        {4, "IV"},
        {1, "I"}
    };
    public string IntToRoman(int num)
    {
        if (!IsValidInput(num))
            return string.Empty;

        StringBuilder result = new StringBuilder();
        foreach (var item in romanLatters)
        {
            while (num >= item.Key)
            {
                result.Append(item.Value);
                num -= item.Key;
            }
        }
        return result.ToString();
    }

    private bool IsValidInput(int num)
    {
        return 1 <= num && num <= 3999;
    }
}

```

> Complexity

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

**Time Complexity**: The time complexity is **O(1)**. This is because the number of Roman numerals is fixed (13 numerals), and the maximum possible number is also fixed (3999). Therefore, the number of iterations does not grow with the size of the input number, making the time complexity constant.

**Space Complexity**: The space complexity is also **O(1)**. The space used by the program does not grow with the size of the input number. The dictionary of Roman numerals uses a constant amount of space, and the `StringBuilder` object `result` will at most hold the Roman numeral equivalent of the number 3999, which is a fixed length string.

Please note that this analysis assumes that dictionary lookups, `StringBuilder` append operations, and integer comparisons/subtractions can be done in constant time.&#x20;