Scale Engineer

Integer to Roman

Med
#0012Time: O(1)Space: O(1)35 companies
Patterns
Math
Data structures
Hash TableString
Companies
AccentureAdobeAgodaAmazon

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through a pre-defined list of Roman symbols and their corresponding integer values, from largest to smallest. For each symbol, we greedily subtract its value from the input number as many times as possible, appending the symbol to our result each time. To handle subtractive cases like 4 (IV) and 9 (IX), we must include these combinations (e.g., 900 for CM, 400 for CD) in our list of symbols.

Algorithm

    1. Define two arrays, values and symbols, which map integer values to their Roman numeral representations. Include subtractive forms (e.g., 900 -> "CM"). Sort them in descending order of value.
    1. Initialize an empty StringBuilder to build the result.
    1. Iterate through the values array from the beginning (largest value).
    1. For each value values[i], use a while loop to check if the input number num is greater than or equal to it.
    1. Inside the while loop, append the corresponding symbols[i] to the StringBuilder and subtract values[i] from num.
    1. Continue this process until num becomes 0.
    1. Convert the StringBuilder to a string and return it.

Walkthrough

We create two parallel arrays: one for the integer values and one for the corresponding Roman symbols. These arrays must be sorted in descending order of value. It's crucial to include the special subtractive forms (900, 400, 90, 40, 9, 4) to ensure the greedy choice is always correct. The algorithm iterates through these values. For each value, it checks if the remaining part of the number (num) is greater than or equal to it. If it is, the corresponding symbol is appended to the result, and the value is subtracted from num. This repeats until num is smaller than the current value. The process continues with the next smaller value until num becomes zero. For example, to convert 1994:

  • Start with num = 1994.
  • Subtract 1000, append "M". num becomes 994.
  • Subtract 900, append "CM". num becomes 94.
  • Subtract 90, append "XC". num becomes 4.
  • Subtract 4, append "IV". num becomes 0.
  • The final result is "MCMXCIV".
class Solution {    public String intToRoman(int num) {        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};                StringBuilder roman = new StringBuilder();                for (int i = 0; i < values.length && num > 0; i++) {            // Greedily append the largest possible symbol            while (num >= values[i]) {                num -= values[i];                roman.append(symbols[i]);            }        }        return roman.toString();    }}

Complexity

Time

O(1)

Space

O(1)

Trade-offs

Pros

  • Elegant and easy to understand.

  • More general and adaptable than hardcoding. If the numeral system were to change, only the mapping arrays would need to be updated.

Cons

  • Slightly less performant in practice than a direct lookup approach due to the looping structure, although both are O(1).

Solutions

public class Solution { public string IntToRoman ( int num ) { List < string > cs = new List < string >{ "M" , "CM" , "D" , "CD" , "C" , "XC" , "L" , "XL" , "X" , "IX" , "V" , "IV" , "I" }; List < int > vs = new List < int >{ 1000 , 900 , 500 , 400 , 100 , 90 , 50 , 40 , 10 , 9 , 5 , 4 , 1 }; StringBuilder ans = new StringBuilder (); for ( int i = 0 ; i < cs . Count ; i ++) { while ( num >= vs [ i ]) { ans . Append ( cs [ i ]); num -= vs [ i ]; } } return ans . ToString (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem