Integer to Roman Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple BlackRock Bloomberg Evernote Facebook Google LinkedIn Microsoft Oracle Twitter Yahoo
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Math StringViews 6358

In this problem, we are given an integer and are required to convert into roman numeral. Thus the problem is generally referred to as “Integer to Roman” and this is Integer to Roman Leetcode Solution. If someone does not know about Roman numerals. In the old times, people did not use integers as we use in recent times.

Roman numerals are usually written from left to right in decreasing order, but there are some exceptions to this. If some numeral which is smaller than the next numeral we subtract the current numeral from the positive sum. A general rule of thumb is not to repeat same numeral more than 3 times. One should check the image below for the integer to roman numeral conversion.

Integer to Roman Leetcode Solution

3
III

Explanation: Since I is equivalent to 1, we repeat it three times to get the sum = 3.

4
IV

Explanation: We cannot repeat I 4 times, because we cannot repeat I more than 3 times. So we plane an I before V. Since I is less than V, thus 1 is subtracted from total which is equal to 5. Thus making a total sum equal to 4.

Approach for Integer to Roman Leetcode Solution

The problem “Integer to Roman” can be solved in greedy manner where first we try to convert the number to the highest possible numeral. The brute force approach to the problem is not possible because it is neither feasible nor generally applicable. In this manner we keep moving to smaller denominations in Roman numeral. But this approach will fail when we try to convert 4. This approach will print 4 times I. So, we need to find a way to get around this.

Well, if we look closely there are only some countable possible ways when we can run into this exception. These exception are only when we repeat some numeral more than 3 times. So just try to find the ways to write the integers which can fall into exception. We get to know that the exception are 4, 9, 40, 90, 400, 900 which can be converted to IV, IX, XL, XC, CD, CM respectively.

Dealing with Exceptions

So, until now we were thinking of converting the given integer to the available original single character roman numerals. But to get around of the exception, we handle them separately. Thus, we create two arrays one which stores the integral value corresponding to each roman numeral. The other array stores the roman numerals. Both of these arrays store the integers and roman numbers at same corresponding indices.

Now, all we are left with is simply using conversion which is done in greedy manner. Start with the largest roman numeral and if the number is greater than the current roman numeral equivalent. Append the roman numeral into an answer string and subtract the integral value from the given integer. Subtract the current number until the given integer is greater than the current number. Once you reach a point when the current number is smaller than the current integer value. Simply check for the next smaller roman numeral. Once we are done with all the roman numerals, we return the answer.

Code for Integer to Roman Leetcode Solution

C++ code for Integer to Roman Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

string intToRoman(int num) {
    vector<string> romans({"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    vector<int> value({1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000});
    int seqSize = romans.size();
    int idx = seqSize - 1;
    string ans = "";
    while(num>0){
        while(value[idx]<=num){
            ans += romans[idx];
            num -= value[idx];
        }
        idx--;
    }
    return ans;
}

int main(){
    cout<<intToRoman(4);
}

IV

Java Code for Integer to Roman Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String intToRoman(int num) {
        String romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int seqSize = romans.length;
        int idx = seqSize - 1;
        String ans = "";
        while(num>0){
            while(value[idx]<=num){
                ans += romans[idx];
                num -= value[idx];
            }
            idx--;
        }
        return ans;
    }
    public static void main(String[] args){
    	System.out.println(intToRoman(4));
    }
}

 

IV

Complexity Analysis

Time Complexity

O(1), because we are using constant number of steps to find the result.

Space Complexity

O(1), since we have stored only constant number of variables and the arrays that we have used also have constant size.

Translate ยป