algoadvance

Leetcode 12. Integer to Roman

Problem Statement

Given an integer, convert it to a Roman numeral.

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX.

There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a Roman numeral.

Clarifying Questions

1. Input Range: What is the range of the input integer?
   • Assumption: The input integer will be in the range from 1 to 3999.
2. Case Sensitivity: Is the Roman numeral output case-sensitive?
   • Assumption: Yes, the Roman numeral output is case-sensitive and should be in uppercase.

Strategy

1. Identify Corresponding Roman Numerals: Create arrays for the integer values that have specific Roman numeral representations (including the special subtractions).
2. Decrement the Integer: Starting from the largest value (1000, “M”), reduce the integer and append the corresponding Roman numeral until the entire integer is converted.

Code

public class IntegerToRoman {
    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 sb = new StringBuilder();
        
        for (int i = 0; i < values.length && num >= 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        
        return sb.toString();
    }

    public static void main(String[] args) {
        IntegerToRoman converter = new IntegerToRoman();
        // Test cases
        System.out.println(converter.intToRoman(3));    // "III"
        System.out.println(converter.intToRoman(4));    // "IV"
        System.out.println(converter.intToRoman(9));    // "IX"
        System.out.println(converter.intToRoman(58));   // "LVIII"
        System.out.println(converter.intToRoman(1994)); // "MCMXCIV"
    }
}

Time Complexity

The time complexity of this approach is O(1) because:

• The maximum number of iterations is fixed as there are only 13 unique symbols (including combinations like IV, IX).
• The while loop within each iteration processes the integer by reducing its value by predefined amounts (from 1000 down to 1), each of which has specific Roman numeral representations.

This constant-time behavior ensures that the solution operates efficiently irrespective of the particular input value within the given range.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?