Python Programming Challenge 8: Integer to Roman

Here’s another challenge from LeetCode (https://leetcode.com/problems/integer-to-roman/).

This challenge requires us to convert integers to roman numerals.

The Roman Numbering System

Let’s first understand how the Roman numbering system works.

In the Roman numbering system, numerals are represented by seven different symbols: I, V, X, L, C, D and M. These symbols stand for 1, 5, 10, 50, 100, 500 and 1000 respectively.

The symbols are written in descending order (largest to smallest) from left to right. All symbols are added together to get the actual number. For instance, DI evaluates to 501 as D + I = 500 + 1 = 501.

ID, on the other hand, is invalid as the symbols are not in descending order (D is not smaller than I).

There are six exceptions to the descending order rule above.

In these 6 exceptions, a smaller symbol can be placed before a larger one. Instead of adding the two symbols together, we subtract the smaller from the bigger.

These 6 exceptions are:

I can be placed before V (5) and X (10) to make 4 and 9 (i.e. IV = 4, IX = 9).

X can be placed before L (50) and C (100) to make 40 and 90 (XL = 40, XC = 90).

C can be placed before D (500) and M (1000) to make 400 and 900 (CD = 400, CM = 900).

Clear?

Examples

Let’s look at some examples:

1. MMDXIII = 2000 (MM) + 500 (D) + 10 (X) + 3 (III) = 2513
2. CDIM is invalid because I cannot come before M
3. CIX = 100 (C) + IX (9) = 109

The Challenge

Our challenge today is to write a function that converts integers into roman numerals.

For instance, if the input is 2513, we should get MMDXIII as the output.

Ready? Try doing it yourself.

Hint:

Let’s consider how we can do it manually.

The roman numeral for 2513 is MMDXIII.

That is because 2513 = 2000 (MM) + 500 (D) + 10 (X) + 3(III)

So the question is, how can we split 2513 into 2000, 500, 10 and 3?

We can use division and modulus (remainder).

1. int(2513/1000) gives us 2. This tells us that there are two ‘1000’s, which translates to ‘MM’.
2. 2513%1000 gives us 513. This removes 2000 from the original number.

We can repeat the two steps above until the entire number is converted. This happens when the remainder is 0.

In other words, the steps for converting 2513 are:

int(2513/1000) = 2
result = 'MM'
2513%1000 = 513

int(513/500) = 1
result = 'MMD'
513%500 = 13

int(13/10) = 1
result = 'MMDX'
13%10 = 3

int(3/1) = 3
result = 'MMDXIII'
3%1 = 0

Using the steps above, try to write a function to convert any integer into roman numerals.

Solution

def intToRoman(num):
    result = ''
    mapping = {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'}

    while num != 0:
        for k, v in mapping.items():
            if num >= k:
                dividend = int(num/k)
                num %= k
                result += dividend*v
    return result

In the solution above, we declare a function called intToRoman() which takes in one argument num.

Within the function, we declare a string called result and assign the empty string to it. Next, we declare a dictionary called mapping to map integers to the 7 roman numeral symbols (M, D, C, L, X, V and I) and 6 exceptions (CM, CD, XC, XL, IX, IV).

This dictionary is arranged in descending order.

Next, we use a while loop that keeps repeating until num equals 0.

Within the while loop, we use a for-loop to loop through the dictionary.

Suppose the number is 2943.

The for loop first checks if 2943>= 1000. As it is, the if-block is executed.

dividend = int(2943/1000) = 2
num = num%k = 2943%1000 = 943
result = result + dividend*v = '' + 2*'M' = 'MM'

After the first step, num equals 943. The for loop proceeds to check if 943 >=900. As it is, the if-block is executed.

dividend = int(943/900) = 1
num = num%k = 943%900 = 43
result = result + dividend*v = 'MM' + 1*'CM' = 'MMCM'

After the second step, num equals 43. The for loop checks if 43 >= 500. As it is not, the if-block is not executed.

The same applies for 43 >= 400, 43 >= 100, 43 >= 90, 43 >= 50.

Finally, when we reach 43 >= 40, the condition evaluates to True again and the if-block is executed.

dividend = int(43/40) = 1
num = num%k = 43%40 = 3
result = result + dividend*v = 'MMCM' + 1*'XL' = 'MMCMXL'

Next, the for loop checks if 3 >= 10, 3>=9, 3>=5, 3>=4. In all four cases, the condition evaluates to False and the if-block is not executed.

Finally, when we reach 3>=1, the if-block is executed.

dividend = int(3/1) = 3
num = num%k = 3%1 = 0
result = result + dividend*v = 'MMCMXL' + 3*I = 'MMCMXLIII'

As num equals 0 now, the while loop ends and we simply return the value of result (MMCMXLIII)

If you run the code and execute the statements below:

print(intToRoman(3217))
print(intToRoman(159))
print(intToRoman(409))

you’ll get the following outputs:

MMMCCXVII
CLIX
CDIX

3217 = 3000 (MMM) + 200 (CC) + 10 (X) + 5 (V) + 2 (II)
159 = 100 (C) + 50 (L) + 9 (IX)
409 = 400 (CD) + 9 (IX)