Integer to Roman

Medium

Bloomberg LP

0 views

Topics:

Greedy AlgorithmsStrings

Seven different symbols represent Roman numerals with the following values:

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

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

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

Constraints:

1 <= num <= 3999

Integer to Roman

Medium

Bloomberg LP

0 views

Topics:

Greedy AlgorithmsStrings

Seven different symbols represent Roman numerals with the following values:

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

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

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

Constraints:

1 <= num <= 3999

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you confirm the input integer will always be a positive integer within the specified range of 1 to 3999?
Are there any specific requirements for handling invalid input, such as numbers outside the 1-3999 range, even though it's stated the input will be within this range?
If multiple Roman numeral representations were somehow possible (though I don't believe they are for standard Roman numerals), which one should I return?
Should the output Roman numeral string be in uppercase or lowercase?
Are there any specific error conditions that I need to handle programmatically, or can I assume the input will always conform to the stated constraints?

Brute Force Solution

Approach

The goal is to convert a regular number into its Roman numeral representation. The brute force method considers all possible combinations of Roman numeral symbols until the correct representation is found. It's like trying out different building blocks to get the right number.

Here's how the algorithm would work step-by-step:

Start by trying to subtract the largest possible Roman numeral value from the input number, such as 1000 (M).
If you can subtract it, add 'M' to your Roman numeral string and reduce the original number by 1000.
Repeat this subtraction as many times as you can with 1000 until the remaining number is less than 1000.
Next, move to the next largest value, like 900 (CM). Try to subtract 900 from the remaining number. If possible, add 'CM' to the string and decrease the number.
Continue doing this for all Roman numeral values (900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, and 1), each time seeing how many times you can subtract the value and adding the appropriate Roman numeral symbols to the string.
Keep going until the original number is reduced to zero. The Roman numeral string you have built up is the result.

Code Implementation

def integer_to_roman(number):
    roman_values = [
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
    ]
    roman_symbols = [
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    ]

    roman_numeral = ""

    # Iterate through each value and corresponding numeral
    for i in range(len(roman_values)):
        # Determine how many times current value can be subtracted
        while number >= roman_values[i]:
            # Append numeral to the result
            roman_numeral += roman_symbols[i]

            # Reduce the input number
            number -= roman_values[i]

    return roman_numeral

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through a fixed set of Roman numeral values (1000, 900, 500, etc.) regardless of the input integer's size. The number of iterations is bound by the number of Roman numeral values, which is a constant. Thus, the time complexity does not depend on the input and is considered constant time, O(1).

Space Complexity

O(1) – The algorithm uses a fixed set of Roman numeral values and their corresponding symbols. It only stores a few variables: the input number, the Roman numeral string being built, and potentially a few loop counters. The size of these variables does not depend on the input number's magnitude; thus, the auxiliary space remains constant regardless of the input. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best way to convert an integer to a Roman numeral is to use pre-defined values for each Roman symbol. We process the integer from largest to smallest place values, finding the corresponding Roman symbol for each value.

Here's how the algorithm would work step-by-step:

First, create a table matching integer values to their corresponding Roman numeral symbols (e.g., 1000 to M, 900 to CM, 500 to D, 400 to CD, and so on, down to 1 to I).
Start with the largest possible integer value in the table and check if it can be subtracted from the input integer.
If it can be subtracted, append the corresponding Roman numeral to the result and decrease the input integer by that amount.
Repeat the previous step until the integer value is larger than the input integer.
Move to the next smaller integer value in the table and repeat the process.
Continue this process until the input integer becomes zero.
The final result is the concatenated Roman numeral string.

Code Implementation

def integer_to_roman(input_integer):
    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'
    }

    integer_values = list(roman_map.keys())
    integer_values.sort(reverse=True)

    roman_numeral = ''

    for integer_value in integer_values:
        # We want to process the largest to smallest values
        while input_integer >= integer_value:
            roman_numeral += roman_map[integer_value]

            # Subtract the integer value from the number
            input_integer -= integer_value

    return roman_numeral

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through a fixed-size table of integer-Roman numeral pairs. The size of this table is independent of the input integer n. The number of iterations is bounded by the number of entries in the table, which is constant. Therefore, the time complexity does not scale with the input and is O(1), constant time.

Space Complexity

O(1) – The provided solution uses a table (which can be implemented as a constant-size array or hash map) to store integer-Roman numeral pairs. The size of this table is fixed regardless of the input integer N. The algorithm also uses a variable to store the resulting Roman numeral string. The length of the string depends on the integer, but the space allocated is bounded by a constant based on the largest representable integer (usually 3999). Therefore, the auxiliary space used is constant, independent of the input integer N.

Edge Cases

Case	How to Handle
Input is 1	The algorithm should correctly return 'I' for the smallest valid input.
Input is 3999	The algorithm should correctly return 'MMMCMXCIX' for the largest valid input.
Input contains a number requiring subtraction (e.g., 4, 9, 40, 90, 400, 900)	Ensure the subtraction logic is correctly applied to handle these cases.
Input is a multiple of 1000 (e.g., 1000, 2000, 3000)	Ensure the algorithm correctly handles multiples of 1000 without mixing with other numeral symbols.
Input close to a subtraction threshold (e.g., 8, 11, 38, 41, 88, 91, 398, 401, 898, 901)	Verify the correct combination of additive and subtractive symbols around these values.
Input that requires many repeated symbols (e.g., 3, 30, 300, 3000)	Ensure that the algorithm doesn't exceed the allowed repetition of each symbol.
Input is 0 or negative	The problem statement specifies input range 1-3999; reject inputs outside this range with an exception or error code.
Non-integer input (e.g., string, float)	Check if input is an integer and throw an exception or return an error code if it is not.