Roman numerals are represented using 7 symbols as follows:

Roman Symbol | Value |
---|---|

I | 1 |

V | 5 |

X | 10 |

L | 50 |

C | 100 |

D | 500 |

M | 1000 |

A Roman numeral has the following properties:

- It is written from left to right in descending order.
**Example**: 2 is written as ‘II’ which is ‘I’+’I’ or 1+1, and 6 is written as ‘VI’ which is ‘V’+’I’ or 5+1. - A character cannot be repeated four times in succession. Subtraction notation is used to represent such instances.
**Example**: 4 is not written as ‘IIII’, rather it is written as ‘IV’. In this case ‘I’ is written before ‘V’ which denotes ‘I’ and should be subtracted from ‘V’ i.e., ‘V’-‘I'(5-1=4).

There are 6 instances where subtraction notation is used:

- ‘I’ is placed before ‘V'(5) to make ‘IV'(4).
- ‘I’ is placed before ‘X'(10) to make ‘IX'(9).
- ‘X’ is placed before ‘L'(50) to make ‘XL'(40).
- ‘X’ is placed before ‘C'(100) to make ‘XC'(90).
- ‘C’ is placed before ‘D'(500) to make ‘CD'(400).
- ‘C’ is placed before ‘M'(1000) to make ‘CM'(900).

# Examples

Input | Output |
---|---|

2 | II |

40 | XL |

1996 | MCMXCVI |

# Solution

### Algorithm:

- Iterate through each symbol/character in the Roman numeral string starting from index 0.
- Get the corresponding integer value of the current symbol.
- If the current value of the symbol is greater than the next value of the symbol, then add this value to the total result. Else, subtract the current symbol value from the total result, if the next symbol value is less than 10 times the current value.

```
using System;
using System.Collections.Generic;
public class DecimalToRoman
{
private Dictionary<int, string> mapping;
private void InitializeDecimalToRomanMapping()
{
if(mapping == null)
{
mapping = new Dictionary<int, string>();
mapping.Add(1000, "M");
mapping.Add(900, "CM");
mapping.Add(500, "D");
mapping.Add(400, "CD");
mapping.Add(100, "C");
mapping.Add(90, "XC");
mapping.Add(50, "L");
mapping.Add(40, "XL");
mapping.Add(10, "X");
mapping.Add(9, "IX");
mapping.Add(5, "V");
mapping.Add(4, "IV");
mapping.Add(1, "I");
}
}
private string IntToRoman(int num)
{
foreach(KeyValuePair<int, string> kv in mapping)
{
if(num >= kv.Key)
return kv.Value + IntToRoman(num - kv.Key);
}
return "";
}
public static void Main(string[] args)
{
var obj = new DecimalToRoman();
obj.InitializeDecimalToRomanMapping();
var input = new int[] {2, 40, 1996};
foreach(int i in input)
{
var result = obj.IntToRoman(i);
if(result == "")
Console.WriteLine ("Please input a number greater than 0");
else Console.WriteLine("Roman Value For "+i+" is : "+result);
}
}
}
```

# Concepts

### Dictionary:

In the above solution, we used a dictionary to store special decimal integers and their corresponding Roman numerals.

- A dictionary is a data structure to hold key-value pairs.
- It is generic and dynamic which means we can create a dictionary of any data type and its size can grow according to our needs.
- Keys cannot be null, but values can be null.
- Duplicate keys are not allowed.

#### Example:

```
Dictionary<int, string> mapping = new Dictionary<int, string>();
mapping.Add(1000, "M");
```

### Recursion:

Recursion is a concept in which a function calls itself until a condition is satisfied. If a recursive function doesn’t have a termination condition, the function will keep on calling itself endlessly.

#### Example:

In the following example, IntToRoman(num) calls itself recursively until it cannot find any key from the mapping smaller than the given parameter number.

```
private string IntToRoman(int num)
{
foreach(KeyValuePair<int, string> kv in mapping)
{
if(num >= kv.Key)
return kv.Value + IntToRoman(num - kv.Key); //recursive call
}
return ""; //recursion termination
}
```

- Recursion should be used only when performance is not a priority.
- The time complexity of a recursive function increases if the number of recursive calls increases.
- It should only be used in cases where time complexity is not an issue and code reduction is a priority.