Introduction

In the last article, we saw how to convert Roman numbers to numeric values. In this article we will do exactly the opposite.

This is leetcode's problem number 12 with difficulty level set to medium. What we did last time is to compare current and next roman characters and perform basic addition and subtraction.

This problem is almost similar with a little extra space. What do I mean by extra space? Well, let's see.

The problem

Here is the problem straight out of Leetcode:

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

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

For example, 2 is written as II in Roman numerals, 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,

Given an integer, convert it to a roman numeral.

Example 1:
Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

The Logic

There are 2 approaches to the solution. The first one with O(n*m) complexity and second one with O(n). Let's see both.

First Approach

The data structure we need for this problem is Dictionary because we need to store Key-Value pairs. Earlier I mentioned we need extra space. We need that extra space to handle these 6 conditions, IV, IX, XL, XC, CD, CM.

We can either use if else statements or switch cases to handle these conditions or simply add these values in the data structure as below.

Dictionary < string, int > romanNumbersDictionary = new() {
    {
        "I",
        1
    }, {
        "IV",
        4
    }, {
        "V",
        5
    }, {
        "IX",
        9
    }, {
        "X",
        10
    }, {
        "XL",
        40
    }, {
        "L",
        50
    }, {
        "XC",
        90
    }, {
        "C",
        100
    }, {
        "CD",
        400
    }, {
        "D",
        500
    }, {
        "CM",
        900
    }, {
        "M",
        1000
    }
};

Listing 1: Roman to Numbers dictionary

For logic all we have to do is to loop through the dictionary in reverse order from large to small number.

Tip: You can save dictionary values stored in reverse order, here just for demonstration I am using the Reverse() method of dictionary.

For each item in the dictionary we need to compare the number and shrink the number with every iteration.

For example, let's take 350 as input,

To understand the flow of execution, refer to this flowchart below. For example, we are using 1994. You can find how we are updating numbers with each iteration.


Figure 1: Flow chart for Integer to Roman

Once you understand the logic code is pretty straightforward. 

internal class NumbersToRoman {
    public string IntToRoman(int num) {
        string romanResult = "";
        Dictionary < string, int > romanNumbersDictionary = new() {
            {
                "I",
                1
            }, {
                "IV",
                4
            }, {
                "V",
                5
            }, {
                "IX",
                9
            }, {
                "X",
                10
            }, {
                "XL",
                40
            }, {
                "L",
                50
            }, {
                "XC",
                90
            }, {
                "C",
                100
            }, {
                "CD",
                400
            }, {
                "D",
                500
            }, {
                "CM",
                900
            }, {
                "M",
                1000
            }
        };
        foreach(var item in romanNumbersDictionary.Reverse()) {
            if (num <= 0) break;
            while (num >= item.Value) {
                romanResult += item.Key;
                num -= item.Value;
            }
        }
        return romanResult;
    }
}

Listing 2: Approach1.cs, Time complexity of O(n * m), Space complexity of O(n)


Figure 2: First approach's success snapshot

Note: This solution is suggested because here you don't have to manually map keys with value. But here we have time complexity of O(n * m), with space complexity of O(n).

We can scale this solution to O(n) but the tradeoff would be to expand the space complexity. Let's do that, for which we need 2 arrays one to hold roman letters and another for numbers.

Second approach

public string IntToRoman(int num) {
    string romanResult = string.Empty;
    string[] romanLetters = {
        "M",
        "CM",
        "D",
        "CD",
        "C",
        "XC",
        "L",
        "XL",
        "X",
        "IX",
        "V",
        "IV",
        "I"
    };
    int[] numbers = {
        1000,
        900,
        500,
        400,
        100,
        90,
        50,
        40,
        10,
        9,
        5,
        4,
        1
    };
    int i = 0;
    while (num != 0) {
        if (num >= numbers[i]) {
            num -= numbers[i];
            romanResult += romanLetters[i];
        } else {
            i++;
        }
    }
    return romanResult;
}

Listing 3: Approach 2, Time complexity of O(n), Space complexity of O(n + m)

In this solution, we have optimized the code with time complexity of O(n), but now space complexity is O(n+m).


Figure 3: Solution 2 success snapshot

It's up to you to choose your own adventure w.r.t. approach.

What I feel is, the second approach could lead to user error. I can easily mismatch elements in either of the arrays while typing. So I will have to keep track of key and value pairs to ensure each key is representing its own value.

For the scope of this problem it's okay as input is limited but if in future input is expanded then it could create a problem.

But that's the discussion for another day. Till then have a good one.