# Integer to Roman **Difficulty:** MEDIUM [External](https://leetcode.com/problems/integer-to-roman) Canonical: https://scaleengineer.com/dsa/problems/integer-to-roman **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Data structures:** Hash Table, String **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Docusign](https://scaleengineer.com/companies/docusign), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Swiggy](https://scaleengineer.com/companies/swiggy), [UiPath](https://scaleengineer.com/companies/uipath), [X](https://scaleengineer.com/companies/x), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Booking.com](https://scaleengineer.com/companies/booking.com), [Geico](https://scaleengineer.com/companies/geico), [NinjaCart](https://scaleengineer.com/companies/ninjacart) --- ## Problem 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 ## Greedy Approach with Symbol Mapping 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. **Time:** O(1) · **Space:** O(1) **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). ### Explanation 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". ```java 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(); } } ``` ### 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. - 2. Initialize an empty `StringBuilder` to build the result. - 3. Iterate through the `values` array from the beginning (largest value). - 4. For each value `values[i]`, use a `while` loop to check if the input number `num` is greater than or equal to it. - 5. Inside the `while` loop, append the corresponding `symbols[i]` to the `StringBuilder` and subtract `values[i]` from `num`. - 6. Continue this process until `num` becomes 0. - 7. Convert the `StringBuilder` to a string and return it. ## Hardcoding with Place Value Lookups This approach leverages the fact that the input integer is constrained (1 to 3999) and that Roman numerals are constructed based on decimal place values. We can pre-calculate the Roman numeral representation for each possible digit (1-9) in each place (ones, tens, hundreds, thousands) and store them in arrays. The final Roman numeral is then constructed by looking up and concatenating the parts. **Time:** O(1) · **Space:** O(1) **Pros:** Extremely fast due to direct lookups and no loops.; Simple to implement once the lookup tables are defined. **Cons:** Less flexible and not easily scalable. It's highly specific to the problem's constraints (1-3999).; The code is more verbose due to the explicit declaration of four arrays. ### Explanation We can break down the conversion into four independent parts: thousands, hundreds, tens, and ones. For each place value, we create a lookup table (an array of strings) that maps a digit (0-9) to its Roman representation. For example, for the tens place, the digit `8` maps to `"LXXX"`, and `9` maps to `"XC"`. The algorithm is as follows: 1. Isolate the thousands digit (`num / 1000`) and look up its Roman string from a `thousands` array. 2. Isolate the hundreds digit (`(num % 1000) / 100`) and look up its Roman string from a `hundreds` array. 3. Isolate the tens digit (`(num % 100) / 10`) and look up its Roman string from a `tens` array. 4. Isolate the ones digit (`num % 10`) and look up its Roman string from a `ones` array. 5. Concatenate these four strings to get the final result. For example, to convert 3749: - Thousands: `3749 / 1000 = 3`. Look up `thousands[3]` -> "MMM". - Hundreds: `(3749 % 1000) / 100 = 7`. Look up `hundreds[7]` -> "DCC". - Tens: `(3749 % 100) / 10 = 4`. Look up `tens[4]` -> "XL". - Ones: `3749 % 10 = 9`. Look up `ones[9]` -> "IX". - Result: "MMM" + "DCC" + "XL" + "IX" = "MMMDCCXLIX". ```java class Solution { public String intToRoman(int num) { String[] thousands = {"", "M", "MM", "MMM"}; String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; return thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10]; } } ``` ### Algorithm - 1. Create four string arrays: `thousands`, `hundreds`, `tens`, and `ones`. - 2. `thousands` array will store `["", "M", "MM", "MMM"]`. - 3. `hundreds` array will store `["", "C", ..., "CM"]` for digits 0-9. - 4. `tens` array will store `["", "X", ..., "XC"]` for digits 0-9. - 5. `ones` array will store `["", "I", ..., "IX"]` for digits 0-9. - 6. Calculate the thousands part by looking up `thousands[num / 1000]`. - 7. Calculate the hundreds part by looking up `hundreds[(num % 1000) / 100]`. - 8. Calculate the tens part by looking up `tens[(num % 100) / 10]`. - 9. Calculate the ones part by looking up `ones[num % 10]`. - 10. Concatenate the four parts and return the resulting string. # Solutions ### CSharp ```csharp 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 (); } } ``` ### Java ```java class Solution { public String intToRoman ( int num ) { List < String > cs = List . of ( "M" , "CM" , "D" , "CD" , "C" , "XC" , "L" , "XL" , "X" , "IX" , "V" , "IV" , "I" ); List < Integer > vs = List . of ( 1000 , 900 , 500 , 400 , 100 , 90 , 50 , 40 , 10 , 9 , 5 , 4 , 1 ); StringBuilder ans = new StringBuilder (); for ( int i = 0 , n = cs . size (); i < n ; ++ i ) { while ( num >= vs . get ( i )) { num -= vs . get ( i ); ans . append ( cs . get ( i )); } } return ans . toString (); } } ``` ### CPP ```cpp class Solution { public: string intToRoman ( int num ) { vector < string > cs = { "M" , "CM" , "D" , "CD" , "C" , "XC" , "L" , "XL" , "X" , "IX" , "V" , "IV" , "I" }; vector < int > vs = { 1000 , 900 , 500 , 400 , 100 , 90 , 50 , 40 , 10 , 9 , 5 , 4 , 1 }; string ans ; for ( int i = 0 ; i < cs . size (); ++ i ) { while ( num >= vs [ i ]) { num -= vs [ i ]; ans += cs [ i ]; } } return ans ; } }; ``` ### Python ```python class Solution : def intToRoman ( self , num : int ) -> str : cs = ( 'M' , 'CM' , 'D' , 'CD' , 'C' , 'XC' , 'L' , 'XL' , 'X' , 'IX' , 'V' , 'IV' , 'I' ) vs = ( 1000 , 900 , 500 , 400 , 100 , 90 , 50 , 40 , 10 , 9 , 5 , 4 , 1 ) ans = [] for c , v in zip ( cs , vs ): while num >= v : num -= v ans . append ( c ) return '' . join ( ans ) ```