# LeetCode 12: Integer to Roman

## Problem Restatement

We are given an integer `num`.

We need to convert it into a Roman numeral string.

Roman numerals use seven base symbols:

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

The input satisfies:

```text
1 <= num <= 3999
```

The LeetCode statement also defines the subtractive forms:

| Value | Roman |
|---:|---|
| 4 | `IV` |
| 9 | `IX` |
| 40 | `XL` |
| 90 | `XC` |
| 400 | `CD` |
| 900 | `CM` |

These are the only subtractive forms used.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `num` |
| Output | A Roman numeral string |
| Constraint | `1 <= num <= 3999` |
| Important rule | Use subtractive notation for `4`, `9`, `40`, `90`, `400`, and `900` |

Example function shape:

```python
def intToRoman(num: int) -> str:
    ...
```

## Examples

Example 1:

```text
num = 3749
```

Break it by place value:

```text
3000 = MMM
700  = DCC
40   = XL
9    = IX
```

Output:

```text
"MMMDCCXLIX"
```

Example 2:

```text
num = 58
```

Break it down:

```text
50 = L
8  = VIII
```

Output:

```text
"LVIII"
```

Example 3:

```text
num = 1994
```

Break it down:

```text
1000 = M
900  = CM
90   = XC
4    = IV
```

Output:

```text
"MCMXCIV"
```

## First Thought: Convert Each Decimal Place

One valid approach is to convert thousands, hundreds, tens, and ones separately.

For example, for `1994`:

```text
1000 -> M
900  -> CM
90   -> XC
4    -> IV
```

This works because Roman numerals are formed from highest place value to lowest place value.

But we can write the same idea more uniformly with a value-symbol table.

## Key Insight

Roman numeral construction is greedy.

At each step, choose the largest Roman value that does not exceed the remaining number.

Append its symbol.

Subtract its value.

Repeat until the number becomes zero.

The important part is to include subtractive forms in the table.

Use this table from largest to smallest:

| Value | Symbol |
|---:|---|
| 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` |

Once the subtractive forms are included, the greedy method naturally produces correct Roman numerals.

## Visual Walkthrough

Use:

```text
num = 1994
```

Start with the largest value.

`1000` fits once:

```text
result = "M"
num = 994
```

`900` fits once:

```text
result = "MCM"
num = 94
```

`90` fits once:

```text
result = "MCMXC"
num = 4
```

`4` fits once:

```text
result = "MCMXCIV"
num = 0
```

Return:

```text
"MCMXCIV"
```

## Algorithm

1. Create a list of `(value, symbol)` pairs from largest to smallest.
2. Create an empty result list.
3. For each `(value, symbol)`:
   - while `num >= value`:
     - append `symbol`
     - subtract `value` from `num`
4. Join the result list into a string.

## Correctness

The value-symbol table contains every standard Roman unit needed for numbers from `1` to `3999`, including all valid subtractive forms.

At each step, the algorithm appends the largest symbol whose value can still be subtracted from the remaining number.

Because Roman numerals are written from larger values to smaller values, this preserves the required order.

The subtractive forms are included before their smaller components. For example, `900` appears before `500` and `100`, and `4` appears before `1`. So the algorithm writes `CM` instead of `DCCCC`, and `IV` instead of `IIII`.

Each append reduces `num` by exactly the value represented by the appended symbol. When `num` reaches `0`, the total value of the output string equals the original input.

Therefore the algorithm returns the correct Roman numeral.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | The input is bounded by `3999`, and the table has fixed size |
| Space | `O(1)` | The output length is bounded |

More generally, the algorithm uses a fixed table of 13 entries.

## Implementation

```python
class Solution:
    def intToRoman(self, num: int) -> str:
        values = [
            (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"),
        ]

        result = []

        for value, symbol in values:
            while num >= value:
                result.append(symbol)
                num -= value

        return "".join(result)
```

## Code Explanation

The table is ordered from largest to smallest:

```python
values = [
    (1000, "M"),
    (900, "CM"),
    ...
    (1, "I"),
]
```

This order is what makes the greedy method work.

For each value-symbol pair:

```python
for value, symbol in values:
```

Append the symbol while it still fits:

```python
while num >= value:
    result.append(symbol)
    num -= value
```

For example, if `num = 3000`, the loop appends `"M"` three times.

Finally:

```python
return "".join(result)
```

This combines the pieces into the final Roman numeral.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.intToRoman(3) == "III"
    assert s.intToRoman(4) == "IV"
    assert s.intToRoman(9) == "IX"
    assert s.intToRoman(58) == "LVIII"
    assert s.intToRoman(1994) == "MCMXCIV"
    assert s.intToRoman(3749) == "MMMDCCXLIX"
    assert s.intToRoman(3999) == "MMMCMXCIX"
    assert s.intToRoman(1) == "I"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `3` | Repeated `I` |
| `4` | Subtractive ones place |
| `9` | Subtractive ones place |
| `58` | Mixed tens, fives, and ones |
| `1994` | Multiple subtractive forms |
| `3749` | Official-style large example |
| `3999` | Maximum allowed input |
| `1` | Minimum allowed input |