DevExplained

12. Integer to Roman

Hash TableMathString

Explanation

To solve this problem, we can iterate over the given integer while reducing it based on the highest Roman numeral value possible at each step. We can create a mapping of Roman numeral symbols to their decimal values and use this mapping to construct the Roman numeral representation of the input integer.

  1. Create a mapping of Roman numeral symbols to their decimal values.
  2. Iterate over the mapping in descending order of decimal values.
  3. At each step, check if the current decimal value can be subtracted from the input integer.
  4. If yes, append the corresponding Roman numeral symbol to the result and subtract its decimal value from the input.
  5. Repeat until the input integer becomes 0.

Time Complexity

The time complexity of this approach is O(1) since the maximum input constraint is 3999, which requires a constant number of operations.

Space Complexity

The space complexity is O(1) as we are using a fixed amount of space for the mapping and the result string.

View Leetcode Problem
class Solution {
    public String intToRoman(int num) {
        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 roman = new StringBuilder();
        
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                roman.append(symbols[i]);
                num -= values[i];
            }
        }
        
        return roman.toString();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question