Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
A complete visual walkthrough of the greedy decomposition approach — from brute force to an elegant table-driven solution.
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 naive approach processes each digit position independently with cascading if/else chains. Extract the thousands, hundreds, tens, and ones, then handle each one separately.
class Solution { public String intToRoman(int num) { StringBuilder sb = new StringBuilder(); // Thousands (only M, up to 3) int thousands = num / 1000; for (int i = 0; i < thousands; i++) sb.append("M"); num %= 1000; // Hundreds (need to handle 400, 500, 900...) int hundreds = num / 100; if (hundreds == 9) sb.append("CM"); else if (hundreds >= 5) { sb.append("D"); for (int i = 5; i < hundreds; i++) sb.append("C"); } else if (hundreds == 4) sb.append("CD"); else for (int i = 0; i < hundreds; i++) sb.append("C"); num %= 100; // Tens — same pattern all over again... int tens = num / 10; if (tens == 9) sb.append("XC"); else if (tens >= 5) { sb.append("L"); for (int i = 5; i < tens; i++) sb.append("X"); } else if (tens == 4) sb.append("XL"); else for (int i = 0; i < tens; i++) sb.append("X"); num %= 10; // Ones — yet again... // ... you get the picture } }
func intToRoman(num int) string { result := "" // Thousands (only M, up to 3) thousands := num / 1000 for i := 0; i < thousands; i++ { result += "M" } num %= 1000 // Hundreds (need to handle 400, 500, 900...) hundreds := num / 100 if hundreds == 9 { result += "CM" } else if hundreds >= 5 { result += "D" for i := 5; i < hundreds; i++ { result += "C" } } else if hundreds == 4 { result += "CD" } else { for i := 0; i < hundreds; i++ { result += "C" } } num %= 100 // Tens — same pattern all over again... tens := num / 10 if tens == 9 { result += "XC" } else if tens >= 5 { result += "L" for i := 5; i < tens; i++ { result += "X" } } else if tens == 4 { result += "XL" } else { for i := 0; i < tens; i++ { result += "X" } } num %= 10 // Ones — yet again... you get the picture return result }
def int_to_roman(num: int) -> str: result = "" # Thousands (only M, up to 3) thousands = num // 1000 result += "M" * thousands num %= 1000 # Hundreds (need to handle 400, 500, 900...) hundreds = num // 100 if hundreds == 9: result += "CM" elif hundreds >= 5: result += "D" + "C" * (hundreds - 5) elif hundreds == 4: result += "CD" else: result += "C" * hundreds num %= 100 # Tens — same pattern all over again... tens = num // 10 if tens == 9: result += "XC" elif tens >= 5: result += "L" + "X" * (tens - 5) elif tens == 4: result += "XL" else: result += "X" * tens num %= 10 # Ones — yet again... # ... you get the picture
fn int_to_roman_verbose(num: i32) -> String { let mut result = String::new(); let mut num = num; // Thousands (only M, up to 3) for _ in 0..(num / 1000) { result.push_str("M"); } num %= 1000; // Hundreds (need to handle 400, 500, 900...) let hundreds = num / 100; if hundreds == 9 { result.push_str("CM"); } else if hundreds >= 5 { result.push_str("D"); for _ in 5..hundreds { result.push('C'); } } else if hundreds == 4 { result.push_str("CD"); } else { for _ in 0..hundreds { result.push('C'); } } num %= 100; // Tens — same pattern all over again... // ... you get the picture result }
function intToRoman(num: number): string { let result = ""; // Thousands (only M, up to 3) const thousands = Math.floor(num / 1000); result += "M".repeat(thousands); num %= 1000; // Hundreds (need to handle 400, 500, 900...) const hundreds = Math.floor(num / 100); if (hundreds === 9) result += "CM"; else if (hundreds >= 5) { result += "D" + "C".repeat(hundreds - 5); } else if (hundreds === 4) result += "CD"; else result += "C".repeat(hundreds); num %= 100; // Tens — same pattern all over again... const tens = Math.floor(num / 10); if (tens === 9) result += "XC"; else if (tens >= 5) { result += "L" + "X".repeat(tens - 5); } else if (tens === 4) result += "XL"; else result += "X".repeat(tens); num %= 10; // Ones — yet again... // ... you get the picture }
The same if/else pattern repeats four times for thousands, hundreds, tens, and ones. It works, but it is verbose, error-prone, and hard to maintain. There must be a better way.
The repeated structure is a signal. Whenever you see the same logic repeated with different constants, that logic can usually be driven by a data table instead of code.
Roman numerals are inherently greedy: always use the largest possible symbol first, then move to smaller ones. The key insight is to include the six subtractive forms (IV, IX, XL, XC, CD, CM) as first-class entries in your lookup table.
All 7 standard symbols + 6 subtractive forms, sorted from largest to smallest:
Why does greedy work here? Roman numerals are designed so that each symbol's value is never more than 10x the next one, and the subtractive forms fill in the gaps. This guarantees that always choosing the largest possible symbol produces the correct (and unique) representation. No backtracking needed.
Start with 1994. Scan the table from left to right. If the current value fits, subtract it and append its symbol. Repeat until the number reaches zero.
Let's trace the greedy algorithm step by step on num = 1994. At each step we check: is num >= current value? If yes, subtract and append. If no, move to the next entry.
Notice the simplicity. One loop, one table, no conditionals about digit positions. The subtractive forms (CM, XC, IV) are handled automatically because they appear in the table before the smaller standard symbols. The algorithm does not even know they are "special."
The greedy algorithm handles all cases uniformly, but it is worth verifying the boundaries.
Why does 3999 work? The table starts with M=1000, and the while loop appends M three times for 3000. Then CM handles 900, XC handles 90, and IX handles 9. The algorithm naturally composes any number in the valid range [1, 3999] without special-casing.
class Solution { public String intToRoman(int num) { // All 13 values: 7 standard + 6 subtractive, descending 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 sb = new StringBuilder(); // Greedy: try each value from largest to smallest for (int i = 0; i < values.length; i++) { // While the current value still fits, keep using it while (num >= values[i]) { sb.append(symbols[i]); // Append the Roman symbol num -= values[i]; // Subtract its value } // When it no longer fits, move to the next smaller value } return sb.toString(); // e.g. "MCMXCIV" for 1994 } }
func intToRoman(num int) string { // All 13 values: 7 standard + 6 subtractive, descending values := []int {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1} symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"} result := "" // Greedy: try each value from largest to smallest for i, v := range values { // While the current value still fits, keep using it for num >= v { result += symbols[i] // Append the Roman symbol num -= v // Subtract its value } // When it no longer fits, move to the next smaller value } return result // e.g. "MCMXCIV" for 1994 }
class Solution: def int_to_roman(self, num: int) -> str: # All 13 values: 7 standard + 6 subtractive, descending pairs = [ (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 = "" # Greedy: try each value from largest to smallest for value, symbol in pairs: # While the current value still fits, keep using it while num >= value: result += symbol # Append the Roman symbol num -= value # Subtract its value # When it no longer fits, move to the next smaller value return result # e.g. "MCMXCIV" for 1994
impl Solution { pub fn int_to_roman(num: i32) -> String { // All 13 values: 7 standard + 6 subtractive, descending let pairs: &[(i32, &str)] = &[ (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"), ]; let mut result = String::new(); let mut num = num; // Greedy: try each value from largest to smallest for &(v, sym) in pairs { // While the current value still fits, keep using it while num >= v { result.push_str(sym); // Append the Roman symbol num -= v; // Subtract its value } // When it no longer fits, move to the next smaller value } result // e.g. "MCMXCIV" for 1994 } }
function intToRoman(num: number): string { // All 13 values: 7 standard + 6 subtractive, descending const pairs: [number, string][] = [ [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"], ]; let result = ""; // Greedy: try each value from largest to smallest for (const [value, symbol] of pairs) { // While the current value still fits, keep using it while (num >= value) { result += symbol; // Append the Roman symbol num -= value; // Subtract its value } // When it no longer fits, move to the next smaller value } return result; // e.g. "MCMXCIV" for 1994 }
Why StringBuilder? String concatenation in a loop creates a new String object each time (O(n) per append). StringBuilder mutates in place, keeping overall construction at O(n) where n is the length of the result (at most 15 characters for 3888 = "MMMDCCCLXXXVIII").
Enter any number from 1 to 3999 and step through the greedy decomposition. Watch which symbol is chosen at each step and how the remaining value decreases.
The outer loop iterates over exactly 13 table entries. The inner while loop runs a bounded number of times per entry (at most 3 for M, C, X, I -- never more). Since the input is constrained to [1, 3999], the total number of operations is bounded by a constant (~39 iterations worst case). The output string is at most 15 characters long.
Four separate if/else blocks handle thousands, hundreds, tens, and ones. Each block runs a bounded number of comparisons and appends. Since the input is capped at 3999, the total work is constant, but the code is verbose with 40+ lines of repetitive branching.
Precomputes four lookup arrays (ones[0..9], tens[0..9], hundreds[0..9], thousands[0..3]) and indexes directly by digit. Each digit position is a single array lookup, giving constant time. The four arrays use fixed storage of roughly 40 entries total.
One outer loop over 13 table entries and an inner while loop that subtracts each value repeatedly. The inner loop runs at most 3 times per entry (for M, C, X, I), capping total iterations at roughly 39. The 13-entry table is fixed-size and the output string is at most 15 characters.
The input is bounded (1-3999), so runtime is constant regardless. All approaches achieve O(1), but the greedy table approach replaces 40+ lines of repetitive if/else logic with a single loop over 13 entries. The "win" here is not speed but clarity and maintainability -- data-driven code over hard-coded branches.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.