Integer to Roman Numeral Editorial

Practice Problem Link: Integer to Roman Numeral

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an integer num, convert it to a roman numeral.

Roman numerals are denoted by a combination of some symbols.

Approach

The idea is to store the numbers (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1) and their roman representation in two different arrays in the same order. Now traverse these arrays and while a value in the array is less than num, append its roman equivalent in the answer string and also subtract the integer value from num. Repeat this process till num is greater than 0.

Analysis

• Time Complexity: O(1)
• Auxiliary Space Complexity: O(1)

Implementation

C++

string integerToRoman(int num) {
        vector<string> romanSymbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        vector<int> values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
	    string roman;
        for (int i = 0; num != 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                roman += romanSymbols[i];
            }
        }
        return roman;
}

Java

class Solution {
    String integerToRoman(int num) {
        String[] romanSymbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        StringBuilder roman = new StringBuilder();
        for (int i = 0; num != 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                roman.append(romanSymbols[i]);
            }
        }
        return roman.toString();
    }
}