Integer to Roman | Leetcode 12 Solution

Converting an integer to a Roman numeral is a common problem in coding interviews and algorithm challenges. In this blog post, we will explore the Leetcode 12: Integer to Roman problem, explain various approaches, and provide Java code solutions for each method.

Problem Statement for Integer to Roman

Given an integer num, convert it into a Roman numeral. The Roman numeral system uses specific characters and combinations to represent values. You are required to return a string representing the integer’s Roman numeral equivalent.

Roman Numerals

The Roman numeral system is based on seven symbols:

For example, the number 1994 is represented as “MCMXCIV”. We can break it down as:

• M = 1000
• CM = 900
• XC = 90
• IV = 4

Thus, 1994 = “MCMXCIV”.

Approach 1: Greedy Algorithm for Integer to Roman

A straightforward approach is to use a greedy algorithm, where we subtract the largest possible Roman numeral value from the given number and keep track of the Roman symbols. We continue this process until the number becomes zero.

Steps:

1. Start with the highest Roman numeral values and their symbols.
2. Subtract the Roman value from the number and append the corresponding symbol to the result.
3. Repeat until the entire number is converted.

Java Code Implementation:

public class IntegerToRoman {
    public String intToRoman(int num) {
        // Arrays for Roman numeral symbols and their corresponding values
        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 result = new StringBuilder();
        
        // Loop through the values array
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                result.append(symbols[i]);
            }
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        IntegerToRoman converter = new IntegerToRoman();
        int num = 1994;
        System.out.println(converter.intToRoman(num));  // Output: MCMXCIV
    }
}

Explanation:

1. Arrays for Values and Symbols: We define two arrays: values[] for Roman numeral values and symbols[] for their corresponding symbols.
2. Greedy Loop: For each Roman numeral, we subtract it from num as many times as possible and append the symbol to the result.
3. Efficiency: This approach runs in O(n) time, where n is the number of Roman numeral symbols (in this case, 13). The space complexity is O(1), as we only use a fixed number of arrays.

Example:

For num = 1994, the function returns “MCMXCIV”.

Approach 2: Using String Concatenation

Another method is to build the Roman numeral as a string, appending values based on the number’s magnitude. This approach is similar to the greedy approach but may involve more manual string management.

Java Code Implementation:

public class IntegerToRoman {
    public String intToRoman(int num) {
        String[] roman = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX", 
                          "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC", 
                          "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM", "M"};
        
        // We break the number down into thousands, hundreds, tens, and ones
        return roman[num / 1000] + roman[(num % 1000) / 100] + roman[(num % 100) / 10] + roman[num % 10];
    }

    public static void main(String[] args) {
        IntegerToRoman converter = new IntegerToRoman();
        int num = 1994;
        System.out.println(converter.intToRoman(num));  // Output: MCMXCIV
    }
}

Explanation:

1. String Array for Roman Numerals: We define an array roman[], where each index corresponds to the Roman numeral representation for values from 0 to 9, 10 to 90, 100 to 900, and so on.
2. Modular Arithmetic: By using division and modulo operations, we break down the number into thousands, hundreds, tens, and ones, then concatenate the appropriate Roman numeral strings.
3. Efficiency: This approach also runs in O(n) time, but with a slightly higher constant factor due to string concatenation.

Example:

For num = 1994, the function returns “MCMXCIV”.

Approach 3: Recursive Solution for Integer to Roman

A recursive solution can be used, where we subtract the largest Roman value and recursively call the function with the reduced number.

Java Code Implementation:

public class IntegerToRoman {
    private final int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private final String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
    public String intToRoman(int num) {
        return helper(num, 0);
    }
    
    private String helper(int num, int index) {
        if (num == 0) {
            return "";
        }
        
        // Subtract the current Roman value and append the corresponding symbol
        if (num >= values[index]) {
            return symbols[index] + helper(num - values[index], index);
        }
        
        return helper(num, index + 1);
    }

    public static void main(String[] args) {
        IntegerToRoman converter = new IntegerToRoman();
        int num = 1994;
        System.out.println(converter.intToRoman(num));  // Output: MCMXCIV
    }
}

Explanation:

1. Recursive Helper Function: The function helper recursively subtracts the largest Roman value from the number and appends the corresponding symbol.
2. Termination Condition: When the number reaches 0, the recursion ends.
3. Efficiency: The time complexity is O(n) and the space complexity is also O(n), due to recursion.

Example:

For num = 1994, the function returns “MCMXCIV”.

Conclusion

In this post, we’ve explored different approaches to solving the Leetcode 12: Integer to Roman problem. We provided three different solutions:

1. Greedy Algorithm: A simple and efficient way to solve the problem with a time complexity of O(n).
2. String Concatenation: A slightly more manual approach that breaks the number into thousands, hundreds, tens, and ones.
3. Recursive Approach: A clean, elegant solution that uses recursion to subtract Roman values.

Each approach is effective, but the greedy algorithm is the most widely used due to its simplicity and efficiency.

I hope this guide helps you in solving the Integer to Roman problem. Feel free to experiment with different approaches and modify the code according to your needs!

Visit for more Leetcode solutions.