Leetcode #12. Integer to Roman

😊 😃 😀 Ave, laicorum conservis !!!🙋‍♂️ 🙋‍♀️🙋

😡 Quid est hoc ineptias !!! 😡

Introduction

Hey, there, fellow reader! Stuck on this tricky medium-level LeetCode problem? No worries, let’s tackle this prompt together with a simple yet effective process. We will first read the prompt and the given examples, take notes on what we understand and jot down any clues we find. Then using our notes, build a solution to pass all the tests. This process should help us understand what we can’t seem to grasp.

Please keep in mind I will be solving this medium-level problem in JavaScript. I encourage you to keep reading, though. The idea being, you can STILL take away something from this read. These problems are meant to test our reasoning and analytical skills, not so much syntax.

Prompt & Examples

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
— — — — — — — — — — — — — — — — — — — — — —
Symbol Value
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
— — — — — — — — — — — — — — — — — — — — — —
For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: “III”

Example 2:

Input: num = 4
Output: “IV”

Example 3:

Input: num = 9
Output: “IX”

Example 4:

Input: num = 58
Output: “LVIII”
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: num = 1994
Output: “MCMXCIV”
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Breaking it down

Oh boy, it looks like this problem is catered to those developer + history dorks 🤓, right? … Ehhh, not really. Remember, no matter how intimidating a problem can seem, there are a few solutions out there for it. The nature of these questions is meant to throw us off guard 🗡 🛡 . Please don’t lose your composure over it; there’s a sound solution in our reach. Find the patterns 🕵️‍♀️ 🕵️‍♂️🕵️ , reflect on what you’ve learned so far. Collective Knowledge + Experience, It’s your greatest tool 🔨 !

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Cool, seven different symbols. They are all unique.

Symbol Value
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

There’s a solution for it. It’s easy to get discouraged by what you read.

Ooooo… nice little chart here. It definitely looks helpful. You probably could store these values in an array or object.

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Now it gets more intense. See the pattern? We have to build the number out of the given symbols. It would be best if you also used the large value symbols as possible. Otherwise, 12 would look like this… “IIIIIIIIIIII. “ Not really efficient or pleasant to read, is it?

Number … Roman Number
2 … II
12 … X + II
27 … X + X + V + II

Let’s jot down this idea. It seems helpful.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five, we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

Gotcha… we build our number left to right. Yet writing numbers like four is interesting. We write are essentially writing a math problem. 1– 5 = 4 or what comes before 4. Odd ️🤷‍♂️ , but I’m sure there’s a good reason for it.

Let’s also jot down the 6 instances of this principle. Also, let’s look at the chart they gave us.

Symbol Value           Number of Instances
I      1
V      5 ← 1–5 = IV    (1)
X      10 ← 1–9 = IX   (2)
L      50 ← …
C      100
D      500
M      1000

Interesting… So given the last part of this text…

- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

We should have all the 6 instances the prompt has mentioned.

Symbol Value             Number of Instances
I =    1
V  =   5 ← 1–5 =         IV ………(1)
X  =   10 ← 1–9 =        IX ………(2)
L  =   50 ← 10–50 =      XL …..(3)
C  =   100 ← 10–100 =    XC …(4)
D  =   500 ← 100–500 =   CD…(5)
M  =   1000 ← 100–1000 = CM.(6)

Let’s update our chart. We will add our 6 cases to it. It should make more sense…

Symbol = Value
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

Cool, This should come in handy later. Let’s be through and look at these examples. Often we can find some interesting insight in them. It’s also a good way to check your own reasoning. We don’t want to waste time being on the wrong train of thought. 🚂

Example 1:

Input: num = 3
Output: “III”

It makes sense when we look at the chart we just updated.

Example 2:

Input: num = 4
Output: “IV”

Yup, it checks out nicely!

Example 3:

Input: num = 9
Output: “IX”

Example 4:

Input: num = 58
Output: “LVIII”
Explanation: L = 50, V = 5, III = 3.

Given the symbols on the chart we just updated, it makes sense. Again, we make the number with the symbols we are given. The largest symbols are on the left and the smallest on the right. 👍

Example 5:

Input: num = 1994
Output: “MCMXCIV”
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Here’s a nice big number! Again we see the largest to the small organization of the symbols, just like before. We are also using our principle here. That’s the IV = 4 logic we read about earlier. Cool 😎 , No major issues or contradictions with our thinking so far! Let’s look at our notes; then, we will start building a solution.

History Note 🧮 : Romans didn’t have negative numbers. To be blunt things were done differenty. So we need to think like a roman, thus it IV is actually 4 NOT -4. Kind of esoteric, but you should see how the Sumerians counted 😜😝😛!

Notes & Clues

Let’s take a look at what we have so far…

• Input: a Number, more importantly, an integer
• Output: a String of Roman Numerals
• Integer = WHOLE NUMBERS, which can be positive or negative
• examples show no negative numbers. Let’s not worry about them.
• Seven different symbols: I, V, X, L, C, D, and M.
• six instances of the given counting principle
• Use updated chart somehow!
• Build the number with given symbols 🔨
• Use the large value symbols as possible.
• Build largest to smallest from left to right.

Writing out the Code

Write off the bat. I can tell you we have a solid upper limit/bound on this problem. The reason being is our symbols and numbers will not increase in size as we scale! This gives us some nice wiggle room.

Let’s start by defining our values and symbols. I want to choose arrays for this as there easy to access, and the size doesn’t grow or shrink. Since we are dealing with HARD-CODED elements, maybe there is something we can do with length…

const intToRoman = function(num) {
const values = [
1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
] < 📏 Has length of 13 📐 …

Now will make another holding just the symbols.

const intToRoman = function(num) {
const values = [
1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
] < 📏 Same length 📐
const symbols = [
“M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”
] < 📏 Same length 📐

…

Hey, these symbols and values are arrays with equal length! That’s really useful. Let’s keep that in mind!

let result = ‘’;

Let’s talk output. We need to return a string with some combo of the symbols in our array. Let make a variable set to an empty string. We will use this to return our answer once our provided function finishes running. 🏃‍♀️ 🏃‍♂️ 🏃

for(let i = 0; i < values.length; i++) {
*stuff in here*
}

We are given a number as an input which is called num. We will also need to use a loop to build our symbols based on the given number.

We have a choice to make at this point; what do we iterate over? Should it be the input (which is a number ) or our arrays? Let’s think about this for a second and think creatively.

Our given input can be any size; thus, any iterating over a number could work. Looking at the constraints at the bottom, the largest number we get is 4 place values. Definitely an option, but it doesn’t sing to me. Let’s look at the other options.

Constraint:

• 1 <= num <= 3999

Our symbols array has no relationship to our given input, so that’s out. That leaves us with our array of numbers called “values,” perhaps checking if we could subtract a number from the array from the given number/input.

We could also store a symbol based on that value to our return variable called ‘results.’ Hmmm… Let’s try that!

Let’s use a good old fashion for loop…

History Note 🧮 : Romans didn’t have zeroes either. Since they followed Ancient Greek reasoning, the idea of having nothing made no sense. Thus it’s reflected in there counting system. Don’t get me started on irrational numbers either… 👊 🥋 🤺

Oh well, in that case, we will have an edge case to worry about! Also, our chart doesn’t have a zero value either. Let’s modify our for loop to reflect that.

… for(let i = 0; i < values.length && num > 0; i++) {
*stuff in here*
} …

See how we are iterating over our values, which is an array of numbers. 👀

for(let i = 0; i < values.length && num > 0; i++) {
while(values[i] <= num) {
}

Now let’s compare each value to the given num/input. Let’s use a while loop for this. We want it to break when our number from the array or value[i] is LESS THAN our number input.

for(let i = 0; i < values.length && num > 0; i++) {
   while(values[i] <= num) {
      *stuff in here*
   }
}

Cool. So the idea is we subtract a value from the input, and we add the symbol that represents that value to our result variable. This works because:

1. Our symbols and values are the same length.
2. They are both organized in an ascending pattern (counting up).

for(let i = 0; i < values.length && num > 0; i++) {
    while(values[i] <= num) {
       num -= values[i];
       result += symbols[i]
    }
}

Looking good so far, let’s return that result variable outside the while loop + for loop combo. All tests should pass!

Solution

const intToRoman = function(num) {
const values = [
1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
]
const symbols = [
“M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”
]
let result = ‘’;
for(let i = 0; i < values.length && num > 0; i++) {
while(values[i] <= num) {
num -= values[i];
result += symbols[i]
   }
  }
  return result
};

Conclusion

Pretty simple solution. Clean and easy to read, yet notice how much time we spent breaking down the problem. That’s super important when tackling intimidating problems like this one. Knowing about roman numerals is a plus, but most of this came from our ability to deduce and what we already know.

Things will eventually click, but the process here is just as important as the clean solution. Stick with a solid approach that prevents you from revisiting the text, isolate what’s tripping you up and drill into it. It’s all target practice, but it isn’t beneficial if you don’t fully understand what’s messing you up. Happy coding! 😆 ⌨️ 🐁

Cool Links Here

leetcode: www.leetcode.com
Roman Numerals: https://en.wikipedia.org/wiki/Roman_numerals
Roman Negative Numbers & Zero: https://www.quora.com/Are-there-negative-Roman-Numerals