12. Integer to Roman
Model: qwen3.5:9b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 57.1%
Problem Breakdown
We need to convert a positive integer (num) into its Roman numeral string representation based on standard rules (additive notation for most values, subtractive notation for specific pairs like IV or IX).
Inputs: A single integer num.
Outputs: A string containing valid Roman characters.
Constraints: The input is guaranteed to be between 1 and 3999 inclusive. This means we don’t need to handle zero, negative numbers, or values exceeding the standard historical range (which would require overlines).
The tricky part isn’t just mapping digits; it’s handling the subtractive cases correctly. For example, if num is 4, we cannot output “IIII”; we must recognize that IV represents a specific value of 4 and handle it as an atomic unit before falling back to I+I+I+I logic.
Intuition
A naive approach might try to process the number digit by digit (e.g., thousands place, hundreds place) or simply subtract standard values like M, D, C repeatedly until zero remains. However, this fails because of the subtraction rules (IV = 4).
If we only map I=1, V=5, X=10 etc., and iterate from largest to smallest, a number like 9 would be processed as IX if we include “IX” in our lookup table before checking for C or D. If we don’t explicitly handle the subtractive pairs (IV, IX, XL, XC, CD, CM) alongside standard values, the greedy logic will incorrectly construct numbers using additive notation where subtraction is required.
The key insight is a Greedy Strategy: Always use the largest possible Roman numeral value that fits into the remaining number at each step. To make this work for subtractive cases, we must define our lookup table to include these special pairs (like 900 -> CM) before their constituent parts (100 -> C).
Approach
- Define a mapping of values to symbols in descending order. Crucially, place the subtraction-based combinations (CM=900, CD=400, XC=90, XL=40, IX=9, IV=4) at their correct positions relative to standard values so they are encountered first during iteration.
- Initialize an empty result string or list builder.
- Iterate through the mapping from largest value to smallest:
- While
numis greater than or equal to the current value in our map, append the corresponding symbol and subtract that value fromnum.
- While
- Return the joined result.
This ensures we greedily pick “M” for 1000s, then handle remaining hundreds (checking CM first), tens (XC/XL/IX/etc.), ones (IV/I).
Complexity Analysis
Time Complexity: relative to input magnitude because the maximum number of iterations is bounded by a small constant derived from the fixed range [1, 3999]. More formally, it’s proportional to the length of the output string (), which is at most ~20 characters. Space Complexity: auxiliary space (excluding input/output storage). We use a static lookup table and a result buffer that doesn’t grow with arbitrary large inputs beyond our constraints.
Solution
class Solution:
def intToRoman(self, num: int) -> str:
# Mapping values to symbols in descending order
# including subtractive cases (CM=900, CD=400 etc.) before standard ones
value_map = [
(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
]
result = []
for value, symbol in value_map:
# While current number can accommodate this value
while num >= value:
result.append(symbol)
num -= value
return "".join(result)
# Example usage (not part of class):
# print(Solution().intToRoman(1994)) # Output: MCMXCIV
Edge Cases Handled
- Minimum Value (
num = 1): The loop processes down toI, correctly returning “I”. - Subtractive Boundaries (
num = 3, 8, 20, 40, 90...): These trigger the specific subtraction logic (e.g., IV for 4, IX for 9) because they are defined in our map before standard additive steps. - Maximum Value (
num = 3999): The loop correctly handles MCMXCIX by processing thousands first, then hundreds with CD/CM checks, etc. - Constraint Bounds: Since input is strictly , we do not handle
0or negative inputs as per problem constraints; the logic assumes valid input range provided in description.