Integer to Roman

Q: What is the time complexity of Integer to Roman?

O(1) . The input is at most 3999, so the greedy loop checks 13 table rows and appends at most 15 symbols. If larger numbers were allowed and written with repeated M , the time would grow with num / 1000 .

Q: Why is 3999 the largest number allowed?

M is the largest letter and no letter may appear four times in a row, so MMM is as far as the thousands go, and 3999 is MMMCMXCIX . Larger numbers were written with extra marks, such as a bar over a letter to multiply it by 1000.

MediumMath and simulation Greedy

+10

Roman numerals have seven letters: M 1000, D 500, C 100, L 50, X 10, V 5 and I 1. Letters go from largest to smallest and add up, so 7 is VII. No letter repeats four times in a row: 4, 9, 40, 90, 400 and 900 are written IV, IX, XL, XC, CD and CM, a smaller letter subtracted from the larger after it. Only these six pairs put a smaller letter first.

Given an integer num, return its Roman numeral.

Function

intToRoman(num: integer) → string

numinteger: an integer from 1 to 3999
Returnsstring: the Roman numeral for num in capital letters

Constraints

1 ≤ num ≤ 3999

Examples

Input: num = 49
Output: "XLIX"
Explanation: 49 is 40 + 9, so the numeral is XL then IX: XLIX. IL is not allowed, because I subtracts only in IV and IX.

Input: num = 2026
Output: "MMXXVI"
Explanation: 2026 has no digit 4 or 9, so no pair is needed and the letters add up: 1000 + 1000 + 10 + 10 + 5 + 1 is MMXXVI.

Input: num = 944
Output: "CMXLIV"
Explanation: 944 is 900 + 40 + 4, and each part is a subtractive pair: CM, XL and IV join into CMXLIV.

Follow-up

Given a string, can you check that it is a Roman numeral in this standard form, accepting XLIX and rejecting IIII, IL and VX?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Add the six subtractive pairs to the alphabet as symbols of their own, and writing a numeral becomes making change: always take the largest value that still fits. The input is at most 3999, so the work is a small fixed amount.

Write it additively, then shorten the long forms

Intuition

Ignore the pairs at first: write as many M as fit, then D, and so on down to I. For 944 that gives DCCCCXXXXIIII. This additive form differs from the standard one only where a digit is 4 or 9, and those spots are always one of six strings with a short form: DCCCC is CM, CCCC is CD, LXXXX is XC, XXXX is XL, VIIII is IX and IIII is IV.

Replace DCCCC before CCCC, or 900 turns into DCD; the same holds in the tens and the ones. The additive form has at most 18 letters (3999), so the work is O(1), paid for with a second pass and a few temporary strings.

Algorithm

For each of the seven letters from M down to I, append it while num is at least its value, and subtract the value each time.
Replace DCCCC with CM, then CCCC with CD.
Replace LXXXX with XC, then XXXX with XL.
Replace VIIII with IX, then IIII with IV.
Return the string.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Greedy over the 13 values

Intuition

Sort the seven letters and six pairs by value: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Taking the largest value that fits is always right. Every value of a lower decimal place is below the smallest value of the place above, so the loop finishes one place before it touches the next. Inside a place, the values for 9, 5, 4 and 1 write each digit the standard way: 9 is the 9 symbol, 5 to 8 are the 5 symbol plus up to three 1 symbols, 4 is the 4 symbol, and 1 to 3 are 1 symbols.

For 3746 the loop writes MMM, D, CC, XL, V, I: MMMDCCXLVI. The table has 13 rows and the answer at most 15 letters, so the work is O(1), in one pass.

Algorithm

List the 13 values with their symbols, from 1000 down to 1, pairs included.
Start with an empty string.
For each row, while num is at least the value, append the symbol and subtract the value.
Return the string once every row is done.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Pitfalls and edge cases

Putting D before CM in the table. 900 then comes out as DCD.
Using if instead of while for each row. 3000 needs M three times; with if it comes out as MCMDCDCXCX.
Inventing other pairs. 99 is XCIX, not IC, and 45 is XLV, not VL.
In C, a buffer that is too small. The longest answer, for 3888, has 15 letters, so it needs 16 bytes with the terminating zero; the additive form needs 19.

Frequently asked questions3

What is the time complexity of Integer to Roman?

O(1). The input is at most 3999, so the greedy loop checks 13 table rows and appends at most 15 symbols. If larger numbers were allowed and written with repeated M, the time would grow with num / 1000.

Can you convert an integer to Roman numerals without a loop over values?

Yes. Keep a table per decimal place with the strings for its digits, such as "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM for the hundreds. Look up each digit of num and join the strings. It is also O(1), with 34 stored strings.

Why is 3999 the largest number allowed?

M is the largest letter and no letter may appear four times in a row, so MMM is as far as the thousands go, and 3999 is MMMCMXCIX. Larger numbers were written with extra marks, such as a bar over a letter to multiply it by 1000.

def intToRoman(num):
    # Write code here

Test #1

Test #2

Test #3

Argument

num = 49

Expected Output

"XLIX"