Coding Interview – Converting Roman Numerals in Python

A common assignment in Python Coding Interviews is about converting numbers to Roman Numerals and vice versa.

Today, we'll look at two possible implementations in Python.

Roman Numerals

Roman Numerals consists of these symbols:

The numbers are constructed by combining these symbols.
For example, the number 22 is represented by: XXII: The symbol with the highest value we can use is X(=10), and we need it twice. Then, we are left with 2 for which we use the symbol I with the value of 1 twice. We end up with XXII for 22.

That's mostly it, but there is one exception. Symbols must not repeat more than twice. So 24 cannot be written as XXIIII, but must be written as XXIV: When there normally would be 4 repeating symbols, these are replaced by the next higher symbol and a substraction symbol in front of it. Our XXIV reads like so:

• Two X
• One V - one I

Converting Numbers to Roman Numerals in Python

def to_roman_numeral(value):
    roman_map = {                                   # 1
        1: "I", 5: "V",,
        10: "X", 50: "L", 
        100: "C", 500: "D",
        1000: "M",
    }
    result = ""
    remainder = value

    for i in sorted(roman_map.keys(), reverse=True):# 2
        if remainder > 0:
            multiplier = i
            roman_digit = roman_map[i]

            times = remainder // multiplier         # 3
            remainder = remainder % multiplier      # 4
            result += roman_digit * times           # 4

    return result

• # 1: We start with a dict containing a translation for each symbol (roman_map).
• # 2: Now, we sort the numerical values in descending order and iterate over these values.
• # 3: Inside the loop, we use an integer division to determine how often we need this particular symbol to repeat.
• # 4: We calculate the missing magnitude of our value by the modulo operation
• # 5: We append the number of symbols to our result string.

Let's see what happens if we convert the number 6:

• First iteration: i = 1000
  • 6 // 1000 = 0
• Second iteration: i = 500
  • 6 // 500 = 0
• Third iteration: i = 100
  • 6 // 100 = 0
• Fourth iteration: i = 50
  • 6 // 50 = 0
• Fivth iteration: i = 10
  • 6 // 10 = 0
• Sixth iteration: i = 5
  • 6 // 1000 = 1
  • result = "V"
  • remainder = 1
• Seventh iteration: i = 1
  • 1 // 1 = 1
  • result = "VI"
  • remainder = 0

That looks good so far. However, we do not obey the rule of not repeating one symbol more than three times with this algorithm.

If times is greater than 3, we need to introduce a special case. Let's think about that for a second.

A repetition of a symbol more than three times can only occur for the symbols I, X, and C. This is because VVVV, LLLL, and DDDD (20, 200, and 2000) would be covered by our algorithm as XX, CC, and MM, anyways.

As a result, we could just attach special symbols to our map instead of introducing a condition in our code:

...
    roman_map = {
        1: "I", 4: "IV", 5: "V", 9: "IX",
        10: "X", 40: "XL", 50: "L", 90: "XC",
        100: "C", 400: "CD", 500: "D",
        900: "CM", 1000: "M",
    }
...

This map would cover all cases of a symbol repeated more than three times.

Converting Roman Numerals to Numbers in Python

def from_roman_numeral(numeral):
    value_map = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    value = 0
    last_digit_value = 0

    for roman_digit in numeral[::-1]:              # 1
        digit_value = value_map[roman_digit]

        if digit_value >= last_digit_value:        # 2 
            value += digit_value         
            last_digit_value = digit_value
        else:                                      # 3
            value -= digit_value

    return value

• # 1: We iterate the Roman Numeral string backwards. If you're not familiar with the [::-1] notation, have a look at my guide on slicing in Python where I cover that in detail.
• # 2:: We check if the digit we are currently looking at is larger than the digit we have looked at before. If it is, we can just add the value we read from our map.
• # 3: If the current digit has a smaller value than the last one, we know that we deal with the special case of not repeating a symbol more than three times. In this case we must substract the value from our result and must not update the last_digit_value.

Your Coding Interview

I hope that this little tutorial helped you with preparing for your Coding Interview in Python. I will add more algorithm examples like this in the future. Stay tuned and check my blog for updates or subscribe to my newsletter! You can also follow me on Twitter.