Integer to Roman

12.Integer to Roman

String

Math

Greedy

Problem Statement:

Convert an integer into a roman numeral. Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Example:

Input:

num = 1994

→

Output:

"MCMXCIV"

Algorithm:

1. Define values and their roman numerals
2. Process in descending order
3. Subtract value and add numeral
4. Continue until number becomes 0

Complexity:

Time: O(1) | Space: O(1)

Java 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();
}

Python Solution:

def intToRoman(self, num: int) -> str:
    # Value-symbol pairs in descending order
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    numerals = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    
    result = ""
    
    for i in range(len(values)):
        while num >= values[i]:
            result += numerals[i]
            num -= values[i]
            
    return result

C++ Solution:

class Solution {
public:
    string intToRoman(int num) {
        const vector<int> values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        const vector symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        string result;
        
        for(int i = 0; i < values.size(); i++) {
            while(num >= values[i]) {
                result += symbols[i];
                num -= values[i];
            }
        }
        
        return result;
    }
};