Integer to Roman [Code + Interactive visualization]

Nov 12

String Medium


def intToRoman(num: int) -> str:
    # Values must be in descending order to build numeral correctly
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    strs = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    
    result = []
    
    # Try each value in descending order
    for i in range(len(values)):
        # While number is greater than current value, subtract and add numeral
        while num >= values[i]:
            result.append(strs[i])
            num -= values[i]
    
    return "".join(result)


class Solution {
    public String intToRoman(int num) {
        // Values must be in descending order to build numeral correctly
        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        StringBuilder sb = new StringBuilder();
        
        // Try each value in descending order
        for (int i = 0; i < values.length; i++) {
            // While number is greater than current value, subtract and add numeral
            while (num >= values[i]) {
                sb.append(strs[i]);
                num -= values[i];
            } 
        }
        
        return sb.toString();
    }
}


class Solution {
public:
    string intToRoman(int num) {
        // Values must be in descending order to build numeral correctly
        vector values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        string result;
        
        // Try each value in descending order
        for (int i = 0; i < values.size(); i++) {
            // While number is greater than current value, subtract and add numeral
            while (num >= values[i]) {
                result += strs[i];
                num -= values[i];
            }
        }
        
        return result;
    }
};

Problem Statement

Given an integer num, convert it to a Roman numeral. Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. The integer is guaranteed to be between 1 and 3999.

Detailed Explanation

Approach

This solution uses a greedy approach, trying the largest possible Roman numeral values first. By including special cases like 900 (CM) and 400 (CD) in our values array, we can handle all cases by simply processing values in descending order.

Key Concepts

Greedy Selection: Always choose largest possible value that fits
Special Combinations: Include subtractive combinations (like CM = 900)
Descending Order: Process values from largest to smallest
Repeated Subtraction: Keep using same value while it fits

Algorithm Steps

Define arrays for values and their Roman numeral representations:
- Values array: [1000, 900, 500, 400, ...]
- Strings array: ["M", "CM", "D", "CD", ...]
- Must be in descending order
For each value in descending order:
- While input number ≥ current value:
  - Append corresponding Roman numeral
  - Subtract value from input number
Return constructed Roman numeral string

Time and Space Complexity

Time Complexity: O(1) - Maximum input is 3999, so loop iterations are bounded
Space Complexity: O(1) - Output size is bounded

Why This Works

The solution works because:

Roman numerals are inherently greedy - we always want the largest possible symbol
By including subtractive combinations, we handle all cases without special logic
Processing in descending order ensures correct symbol placement
While loop handles repeated symbols (like III) naturally

Edge Cases

Input = 1: Single symbol "I"
Input = 3999: Maximum case "MMMCMXCIX"
Numbers requiring subtractive notation (like 9, 40, 900)
Numbers requiring repeated symbols (like 3000 = "MMM")

Common Mistakes

Not including subtractive combinations in values array
Processing values in wrong order
Not handling repeated symbols properly
Trying to build complex logic for subtractive cases

Integer to Roman - Interactive Visualization

Input Number

1994

Current Value

Remaining