Leetcode 12: Integer to Roman [Solution]

This question is really very much similar to the manual approach, so just do the same you do in real life to convert a number to roman but this time with code.

Difficulty: Medium
Jump To:

• Problem Statement
• Explanation
• Solution
• Algorithm
• Implementation

Problem Statement

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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

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.

Example 1:

Input: num = 3
Output: "III"

Example 2:

Input: num = 4
Output: "IV"

Example 3:

Input: num = 9
Output: "IX"

Example 4:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= num <= 3999

Explanation

So any natural number can be converted into Roman Numeral but as the number goes bigger the roman representation gets longer. Firstly just have a look at the constraints part, So the problem statement is clear that we need to convert the numbers below 4000 only. So how do we convert a number to roman in real life? Just do the same here or a slightly modified version to make it faster.

Solution

Roman Numerals are usually written in the form of Larger to Smaller Numeral and a character can be contiguously repeated by 3 times maximum eg. 1=I, 2=II, 3=III but 4!=IIII, it's 4=IV. So writing a numeral multiple times means we are adding those numerals but whenever a smaller numeral comes before a bigger numeral, it means that we need to subtract smaller numeral from the bigger one.
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II but 19 is written as XIX i.e. X + IX.

So the separate numerals of the number are added to form the complete numeral for the whole number. As in roman numeral, we write from larger to smaller to we'll first try to write the larger numeral first.
Let's understand that in this way, for example, we need to convert 8 so we'll try to write it as 5 + 3 which will result in VIII but if I don't try to go with the larger number first then I might write it as 3 + 5 i.e. IIIV which is wrong.

So it's clear we need to break the number in a way that we get the roman numeral for the bigger part first. To do this we can create an ordered map of number -> roman numeral and try to reduce the number in a way that we extract the biggest numeral from the number and when the number can't be written with the biggest numeral then we'll try the next biggest numeral. While extracting we'll be concatenating the numerals.

Algorithm:

1. Create an ordered dictionary of integer to the roman numeral for 1 character and 2 characters (eg. 4,9, 40, etc) roman numerals ordered by numerical value descending.
2. Point to the first(largest) element of this dictionary.
3. while num>0 repeat
   1. if num >= numerical value pointing by the pointer, then add the string for this numerical value to the answer and deduct this numerical value from the number.
   2. Else move the pointer forward to point to the next biggest value in the dictionary.
4. Return answer string.

Time Complexity: O(n)
Space Complexity: O(1)

Implementation

C++ Code:

class Solution {
public:
    string intToRoman(int num) {
        // Prepare ordered dictionary with array and pair
        pair<int,string> rmap[] = {
            {1000,"M"}, 
            {900,"CM"}, 
            {500, "D"}, 
            {400, "CD"}, 
            {100, "C"}, 
            {90, "XC"}, 
            {50, "L"}, 
            {40, "XL"}, 
            {10,"X"},
            {9,"IX"},
            {5, "V"}, 
            {4,"IV"}, 
            {1, "I"}
        };

        // Initialize pointer to the beginning of the array
        int rptr = 0;
        string str="";
        // Loop till the number is above 0
        while(num){
            // If numeric value at pointer is >= the number
            if(num>=(rmap[rptr]).first){
                // Add numeral to the answer
                str += (rmap[rptr]).second;
                // subtract numeric value from the number
                num -= (rmap[rptr]).first;
            }
            else{
                // Move pointer to the next biggest numeric value
                rptr++;
            }
        }
        return str;
    }
};

Runnable C++ Code:

Cover Image by Shawn Lee on Unsplash