In this article, we will solve the Integer to roman leet code problem. First, we will see the problem definition, and then we will discuss the technique and then jump to the coding part. Problem link: https://leetcode.com/problems/integer-to-roman/
Note: This is not the efficient solution for this problem, but it will be easy to explain what’s happening and why it’s happening with this solution. If you have a better solution don’t hesitate to comment 😉
Problem description:
First we will break the problem and get the facts.
- The problem is we have to convert a given number to roman numerals.
- Roman numerals have only 7 characters, we can see this above ( I, V, X, L, C, D ).
- And they have exceptions too, for 4, 9, 40, 90, and 900.
Technique:
In this section we will see how to approach this problem.
- Say our input is 23, then the respective roman number will be XXII, in other words, 10+10+3.
- Another example 87, roman number will be LXXXVII, which is 50+10+10+10+5+1+1 ( refer to this link for conversion ).
- See the pattern? we have to split the input numbers to the available roman numbers first ( 5, 10, 50, 100, 500, 1000 ) and convert them to their respective roman numerals and concatenate them.
before we jump into the coding part we must be familiar with a couple of concepts.
Recursion:
Recursion is a technique where you call a function with the same function ( speaking about calling, check out my tutorial on creating your own video chat app, follow this link ).
example:
let i=0;
function display(){
if(i<5){
console.log(i)
i++;
display()
}else{
return;
}
}
the above code will print 0,1,2,3,4. When the condition fails( i<5 ), I am returning to the previous function that called this function.
Hash table:
This is the same as JSON in javascript ( key value pair ).
example:
{
name:”John”,
age:21
}
Code ( Solution ):
- In the first section, we declare all known roman numbers in a hash table ( Note we have added additional values to make our solution easy ).
- programInput contains our input ( the number that needs to be converted to Roman numbers ), we convert that to string and store the length in inputLength variable.
- ranges contain all the keys of our hash table and Infinity ( will discuss why in a bit ).
Note: We are mapping all the keys to integer because by default in js all the keys are string.
- In the while loop section we are spliting our input using modulus operation
example:
the spliting works like this: if the input is 123, then after splitting it would be 100, 20 and 3.
Next we will see what happens in the rangeCalculator function.
Note: Below when we say input we are referring to the parameter input
- The first loop finds to which range the input belongs ( i.e, 50-100, 100-500, or above 1000 ).
- When the input goes above 1000 then the range will be 1000 to Infinity.
- We take the starting number in a range as the current range and assign it to the range variable.
- then “input%range === 0” will find if the input is divisible by our range value.
- if yes then we create an array and fill it with the corresponding Roman numeral.
example:
if the input value is 20, then it comes in the range of 10 to 50 so our current range will be 10 ( starting number ), so according to the code above the array will have length 2( 20/10 ) with the value “XX” ( Roman number for 10 is X ).
- If no ( else part ) then we append the roman number of the starting range and subtract it from the input then call rangeCalculator recursively.
example:
if the input variable has the value 13 ( range 10 to 20 ), we have a 10 for sure so we include X.
Program stops when the InputLength is 0.
Result:
Input: 123
Output: CXXIII
Gist: https://gist.github.com/kishork2120/4abbd42488be554fbe57b4feef2c94ff#file-program-js
Happy coding!!!