Given a roman numeral as input, write a function that converts the roman numeral to a number and outputs it. When a smaller numeral appears before a larger one, it becomes a subtractive operation. You can assume only one smaller numeral may appear in front of larger one. For example: if given the input VI, the output should be 6 (5 + 1 = 6) or if given the input IV, the output should be 4 (5–1 = 4).
One of our biggest challenges here is knowing if we should be adding the current letter within the roman numeral or subtract it. I decided that, while iterating through, I could peak to the right of the current letter and decide whether to add or subtract. This route would give me a linear time complexity at worst case. Let’s take a look at the pseudocode.
The time complexity of the above algorithm should be the same as the number of items produced. This is because as the list grows larger, we have to continue to check each letter to add the value. Therefore, with an input size of n the time complexity is linear — O(n).
Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.
I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!