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:
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).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 <= 3999The key idea behind solving Integer to Roman is understanding how Roman numerals are constructed using specific value-symbol pairs. Instead of building the numeral digit by digit, an efficient strategy is to use a greedy approach. Prepare an ordered mapping of integer values to their corresponding Roman symbols (for example 1000 -> M, 900 -> CM, 500 -> D, etc.).
Starting from the largest value, repeatedly subtract the value from the given number while appending the corresponding symbol to the result string. This works because Roman numerals always prefer the largest possible symbol at each step, including special subtractive combinations such as IV, IX, XL, and CM. By iterating through this predefined list and reducing the number accordingly, you gradually construct the final Roman numeral.
Since the mapping contains a fixed set of symbols, the algorithm runs in near constant time with minimal extra memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy mapping with value-symbol pairs | O(1) (bounded by fixed Roman symbols) | O(1) |
NeetCode
This approach utilizes a greedy strategy by iterating over an ordered list of numeral values and corresponding symbols. Starting from the largest value, it repeatedly subtracts from the given number until the result is less, appending the equivalent symbol each time. This ensures the numeral is created with the fewest characters.
Time Complexity: O(1) — The solution has a fixed iteration through a constant list of length 13, hence it's O(1).
Space Complexity: O(1) — Uses constant space for the result string and numeral arrays.
1#include <stdio.h>
2#include <string.h>
3
4char* intToRoman(int num) {
5 static char result[20]
The C implementation defines an array of integer values and corresponding Roman symbols. A loop iterates through these values, subtracting the largest possible from the input number, and appends the associated Roman symbol to the result string.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Integer to Roman problem appear in technical interviews at large tech companies. It tests understanding of greedy algorithms, string manipulation, and handling predefined mappings.
The optimal approach uses a greedy strategy with a predefined mapping of integer values to Roman symbols. By iterating from the largest value to the smallest and subtracting while appending symbols, you construct the correct Roman numeral efficiently.
A simple ordered list or array of value-symbol pairs works best. It allows you to iterate through the values from largest to smallest and build the Roman numeral by repeatedly subtracting and appending symbols.
Roman numerals use subtractive notation for certain numbers to avoid four identical symbols in a row. For example, 4 is written as IV instead of IIII, and 9 is written as IX instead of VIIII.