This post is completed by 1 user

  • 0
Add to List
Medium

386. Convert Integer to Roman

Objective: Given an Integer, write a program to convert it to Roman number.

This problem can be stated as "Convert Decimal to Roman String" OR "Convert numeral value to Roman numeral".

Roman Number -   Letters used in Roman numerals and the corresponding numerical values are given in the table below.

Rules:

Roman numerals are usually written in highest to lowest from left to right except for some special cases where the left character is less than the right character. for example 'IV' is equivalent to 4 not 'IIII'. In such cases, subtract the left character value from the right character value. 'IV' will be 5-1 = 4, same for 'IX' = 10-1 = 9. Below are the cases -

  1. I can be placed before V or X, represents subtract one, so IV (5-1) = 4 and 9 is IX (10-1)=9.
  2. X can be placed before L or C represents subtract ten, so XL (50-10) = 40 and XC (100-10)=90.
  3. C placed before D or M represents subtract hundred, so CD (500-100)=400 and CM (1000-100)=900.

Example:

Integer: 25
Roman: XXV
---------------------------------------------------
Integer: 36
Roman: XXXVI
---------------------------------------------------
Integer: 1023
Roman: MXXIII
---------------------------------------------------
Integer: 542
Roman: DXLII

Approach:

Store Letters used in Roman numerals and the corresponding numerical values in an array. Initialize a string builder, Now start checking if input number is >= highest roman numeral then add it to the string builder and reduce its corresponding value from the input number and if input number is < highest roman numeral then check with next highest roman numeral and repeat the process above till input number becomes 0. string builder will be our roman representation of input number.

Walk Through: 

N = 36
values = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
String[] romanLiterals = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"];
result =""

1000>36, check with next roman numeral, result =""
900>36, check with next roman numeral, result =""
500>36, check with next roman numeral, result =""
400>36, check with next roman numeral, result =""
90>36, check with next roman numeral, result =""
50>36, check with next roman numeral, result =""
40>36, check with next roman numeral, result =""
10<36, add corresponding literal 'X' to result , result =X, N = 36-10=26
10<26, add corresponding literal 'X' to result , result =XX, N = 26-10=16
10<16, add corresponding literal 'X' to result , result =XXX, N = 16-10=6
10>6, check with next roman numeral, result =XXX
9>6, check with next roman numeral, result =XXX
5<6, add corresponding literal 'V' to result , result =XXXV, N = 6-5=1
5>1, check with next roman numeral, result =XXXV
4>1, check with next roman numeral, result =XXXV
1==1, add corresponding literal 'I' to result , result =XXXVI, N = 1-1=0

Result = XXXVI

Output:

Integer: 25
Roman: XXV
---------------------------------------------------
Integer: 36
Roman: XXXVI
---------------------------------------------------
Integer: 1023
Roman: MXXIII
---------------------------------------------------
Integer: 542
Roman: DXLII
---------------------------------------------------