How to solve LeetCode problem #12 Integer to Roman
Javascript – LeetCode problem #12 Integer to Roman
In this problem, we need to create a method that translates an Integer (1<=n<=3999) to a Roman numeral. Read the full problem on LeetCode.
Pattern – Deconstruct the Integer
The key to solving this problem is understanding the construction pattern of Roman numerals:
- They are read as a sum of their parts and are generally written largest to smallest (thousands, hundreds, tens, singles)
- => we need to deconstruct the Integer to thousand, hundreds, tens, singles
- 3210 => 3 thousands, 2 hundreds, 1 ten, 0 singles => MMMCCX
- => we need to deconstruct the Integer to thousand, hundreds, tens, singles
- however, we need to keep the exception in mind where a number in a threshold position is represented by subtraction:
- I = 1; II =2; III =3; IV=4; V=5
- V=5; VI = 6; VII=7; VIII =8; IX =9; X =10
- X=10; XX=20; XXX =30; XL =40; L = 50
- 2439 => 2 thousands, 4 hundreds, 3 tens, 9 singles => MMCDXXXIX
In summary, we need to look at each digit of the Integer and its “weigth” (thousands, hundres, etc.), then determine the correct Roman numeral to represent it.
Solution – Integer to Roman
Mapping values and preparing the main method
For my solution, I first setup a map that maps each “range” (hundreds, tens, singles) to the Roman numerals can be used to construct a number in that range.
const romanMap = new Map([
//hundreds
["C", {
top : "M", //1000
mid : "D", //500
self : "C" // 100
}],
//tens
["X", {
top : "C", // 100
mid : "L", // 50
self : "X" // 10
}],
//singles
["I", {
top : "X", // 10
mid : "V", // 5
self : "I" // 1
}],
]);
Example:
Looking at section singles, every number between 1-9 can constructed with the letters listed under "I" (I,V,X)
1=I, 2=II, 3=III, 4=IV, 5=V, 6=VI, 7=VII, 8=VIII, 9=IXNext, I am working on the function itself. I’m initializing my output in var romanStr as an empty string. Because we need to separately evaluate each digit of the integer, I am converting the Integer (num) to a string and then splitting it into an array (arrNum). I’m also grabbing the length of the resulting array (arrLength).
As a first condition, if the array is empty, we can return an empty string.
var intToRoman = function(num) {
let romanStr = "";
let arrNum = num.toString().split("");
let arrLength = arrNum.length;
if(arrLength===0){
return romanStr;
}
}
Example:
num=432
num.toString()= "432"
num.toString().split("") = ["4","3","2"]Let’s work on the additional conditions for checking the array. We already know if the array is empty, we have nothing to evaluate and return an empty string. Additionally we know:
- if the array length is 4, we have a number with 4 “sections” (thousands, hundreds,tens,singles)
- if the array length is 3, we have a number with 3 “sections” (hundreds, tens, singles)
- if the array length is 2, we have a number with 2 “sections” (tens, singles)
- if the array length is 1, we have a number with 1 “section” (singles)
As seen below, processing thousands is pretty straightforward. The problem constraints state the n <= 3999, which means we can just add an M to our romanStr for each digit at the 0th index of arrNum.
if(arrLength===0){
return romanStr;
}
else if(arrLength == 4){
// process thousands
for(let i=0; i <arrNum[0]; i++){
romanStr += "M";
}
// process hundreds, tens, singles
}
else if(arrLength == 3){
// process hundreds, tens, singles
}
else if(arrLength == 2){
// process tens, singles
}
else {
// process singles
}
Example:
num= 3201
numArr = ["3","2","0","1"]
arrLength = 4
arrNum[0] = 3
=> for loop adds 3 "M"s to our string
romanStr = "MMM"Creating a helper method
To process hundreds, tens and singles, we need some more complex logic to allow for specially constructed numerals. For this, I created a helper function getRomanRep(n,type). n is the digit we are evaluating and type is the digits “weight” that we have mapped at the very start. For example, n=3 type=X means we are evaluating 3 in the space of tens, aka 30. n=7 type=C means we are evaluating 7 in the space of hundreds, aka 700.
In this helper function, we need one more if…else statement that evaluates n and then uses its type to get the correct letters to construct the Roman numeral representation.
- n>0 && n<=3 | this is the simplest construction, add the corresponding letter from the map n-times
- n=2, type = X ; we are getting section X from the map, then selecting the .self value (X) and adding it n-times => “XX” or 20
- n==4 | we need to construct this Roman numeral as a combination of letters
- n=4, type = C; we are getting section C from the map and adding a .self value (C) before the .mid value (D) => “CD” or 400
- n==5 | we need to construct this Roman numeral by taking the mid value of its mapped values
- n=5, type = I; we are getting section I from the map and adding .mid value (V) => “V” or 5
- n>5 && n<9 | we need to construct this Roman numeral by taking the .mid value and adding (n-5) .self values
- n=7, type=X; we are getting section X from the map, first add .mid value (L) and then 2 .self values (X) => “LXX” or 70
- n==9 | we need to construct this Roman numeral as a combination of letters
- n=9, type = C; we are getting section C from the map and adding a .self value (C) before the .top value (M) => “CM” or 900
function getRomanRep(n,type){
let strOut = "";
if(n>0 && n<=3){
for(let i=0; i<n; i++){
strOut += romanMap.get(type).self;
}
}
else if(n==4){
strOut += romanMap.get(type).self;
strOut += romanMap.get(type).mid;
}
else if(n==5){
strOut = romanMap.get(type).mid;
}
else if(n>5 && n<9){
strOut += romanMap.get(type).mid;
for(let i=0; i<n-5; i++){
strOut += romanMap.get(type).self;
}
}
else if(n==9){
strOut += romanMap.get(type).self;
strOut += romanMap.get(type).top;
}
return strOut;
}
Full Solution – Integer to Roman
Now it’s time to put it all together! In our main method intToRoman(), I am now calling the helper method for each digit that needs to be evaluated and passing through the correct map key (“C” for hundreds, etc.). Each evaluation adds to romanStr which I am returning at the end. See the full code below:
const romanMap = new Map([
//hundreds
["C", {
top : "M", //1000
mid : "D", //500
self : "C" // 100
}],
//tens
["X", {
top : "C", // 100
mid : "L", // 50
self : "X" // 10
}],
//singles
["I", {
top : "X", // 10
mid : "V", // 5
self : "I" // 1
}],
]);
var intToRoman = function(num) {
let arrNum = num.toString().split("");
let arrLength = arrNum.length;
let romanStr = "";
if(arrLength === 0){
return romanStr;
}
else if(arrLength == 4){
for(let i=0; i <arrNum[0]; i++){
romanStr += "M";
}
romanStr += getRomanRep(arrNum[1],'C');
romanStr += getRomanRep(arrNum[2],'X');
romanStr += getRomanRep(arrNum[3],'I');
}
else if(arrLength === 3){
romanStr += getRomanRep(arrNum[0],'C');
romanStr += getRomanRep(arrNum[1],'X');
romanStr += getRomanRep(arrNum[2],'I');
}
else if(arrLength === 2){
romanStr += getRomanRep(arrNum[0],'X');
romanStr += getRomanRep(arrNum[1],'I');
}
else{
romanStr += getRomanRep(arrNum[0],'I');
}
return romanStr;
};
function getRomanRep(n,type){
let strOut = "";
if(n>0 && n<=3){
for(let i=0; i<n; i++){
strOut += romanMap.get(type).self;
}
}
else if(n==4){
strOut += romanMap.get(type).self;
strOut += romanMap.get(type).mid;
}
else if(n==5){
strOut = romanMap.get(type).mid;
}
else if(n>5 && n<9){
strOut += romanMap.get(type).mid;
for(let i=0; i<n-5; i++){
strOut += romanMap.get(type).self;
}
}
else if(n==9){
strOut += romanMap.get(type).self;
strOut += romanMap.get(type).top;
}
return strOut;
}
This is how I solved LeetCode problem #12 Integer to Roman in Javascript. See other LeetCode solutions
