Leetcode – 12 – Integer to Roman

Integer to Roman

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Description:

In this problem we have to convert the given number to its corresponding roman numerals.

Brute Force Logic:

At first we need to know what are the Roman numerals available and their corresponding mapping decimal value.

For eg. 3 maps to III, 4 maps to IV, 5 maps to X and so on. upto 3999.

We can find a pattern in this that the unique roman numerals are

I, V, X, L, C, D, M corresponds to 1,5,10,50,100,500,1000

We also observe that some of these symbols are used to represent some numbers along with other combinations.

for ex.

  • I for 1 is used to represent upto 1,2,3 [I,II,III]
  • V for 5 is used to represent 4 by writing like IV, VI, VII, VIII [4,6,7,8]
  • X for 10 is used for IX, XI, XII, XII … XXXIX [9,11,12,13… 39]
  • L for 50 is used for XL, LI… LXXXIX [40 to 89]
  • ..

With this we can conclude that with repeated modulo with the corresponding decimal value and storing the values we can get the correct roman numerals

Efficient solution: (repeated modulo corresponding to roman numerals)

The solution is to have the compare with the decimal value and append the roman literals accordingly.

  • add ‘I’ if the number is less than 4
  • take the module of 4 which returns 1 call the function again to append ‘I’ and then append it with ‘V’ for 4
  • for numbers between 5 and 9 we will have to append ‘X’ after taking modulo of 5
  • continue similar logic upto 10 after that we will have to take the difference of 10,40,50,90,100,400,500,1000

1

Code:

public class Solution {
    public String intToRoman(int num) {
        // I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1,000
        StringBuilder s = new StringBuilder();
        if(num > 0){
            if(num < 4){
                s.append("I");
                num = num-1;
                s.append(intToRoman(num));
            }
            if(num == 4){
                num = num % 3;
                s.append(intToRoman(num));
                s.append("V");
            }
            if(num >= 5 && num < 9){
                s.append("V");
                num = num % 5;
                s.append(intToRoman(num));
            }
            if(num == 9){
                num = num % 8;
                s.append(intToRoman(num));
                s.append("X");
            }
            if(num >= 10 && num < 40){
                s.append("X");
                num = num - 10;
                s.append(intToRoman(num));
            }
            if(num >= 40 && num <= 49){
                s.append("XL");
                num = num - 40;
                s.append(intToRoman(num));
            }
            if(num >= 50 && num <= 89){
                s.append("L");
                num = num - 50;
                s.append(intToRoman(num));
            }
            if(num >= 90 && num <= 99){
                s.append("XC");
                num = num - 90;
                s.append(intToRoman(num));
            }
             if(num >= 100 && num <= 399){
                s.append("C");
                num = num - 100;
                s.append(intToRoman(num));
            }
            if(num >= 400 && num <= 499){
                s.append("CD");
                num = num - 400;
                s.append(intToRoman(num));
            }
            if(num >= 500 && num <= 899){
                s.append("D");
                num = num - 500;
                s.append(intToRoman(num));
            }
            if(num >= 900 && num <= 999){
                s.append("CM");
                num = num - 900;
                s.append(intToRoman(num));
            }
            if(num >= 1000 && num <= 3999){
                s.append("M");
                num = num - 1000;
                s.append(intToRoman(num));
            }
        }
        return s.toString();
    }
}

Time Complexity: O(n)

  • Go through all the digits – O(n)

Space Complexity: O(1)

  • We will append the roman characters one by one  – O(1)

Available Test Cases: 3999

  • handle for each unique roman characters
    I 1
    IV 4
    V 5
    IX 9
    X 10
    XL 40
    L 50
    XC 90
    C 100
    CD 400
    D 500
    CM 900
    M 1000

 Github:

Leetcode_12_Integer_to_Roman

1 comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: