roman-numerals.js

function toRoman(num) {
  if (num === 0) return "";
  let numerals = {
    M: 1000,
    CM: 900, D: 500, CD: 400, C: 100,
    XC: 90, L: 50, XL: 40, X: 10,
    IX: 9, V: 5, IV: 4, I: 1,
  };
  
  for (const [key, value] of Object.entries(numerals))
    if (num - value >= 0) return key + toRoman(num - value);
}

console.log(toRoman(128)); // should return "CXXVIII"
console.log(toRoman(2000)); // should return "MM"
console.log(toRoman(2017)); // should return "MMXVII"
console.log(toRoman(1999)); // should return "MCMXCIX"

roman_numeral_recursion.md

Prompt

Write a recursive function that converts an integer into a string such that the number is represented in Roman Numerals in the most efficient way. eg, the number 4 could be written as 'IIII' but it's more efficient to use 'IV' since that's a shorter string Assume no number is greater than 4,000 Here are the Roman Numeral equivalents you'll need to know:

• M=1000
• CM=900
• D=500
• CD=400
• C=100
• XC=90
• L=50
• XL=40
• X=10
• IX=9
• V=5
• IV=4
• I=1

Rewrite the question in your own words:

Write a recursive function that takes in a number (<= 4000) and converts it to the shortest possible string of roman numerals.

What assumptions will you make about this problem if you cannot ask any more clarifying questions? What are your reasons for making those assumptions?

• There probably won't be negative numbers or zeroes (roman numberals don't really have a way of dealing with either of those)

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

One way to do it is to maybe start by going through every entry in a hash and subtracting the numerical equivalent from the number, and if it's still greater than 0 then recurse by passing through the number minus the numeral

How would you identify the elements of this problem?

• Searching of Data
• Sorting of Data
• Pattern Recognition
• Build/Navigate a Grid
• Math
• Language API knowledge
• Optimization

Which data structure(s) do you think you'll use? What pros/cons do you see with that choice?

• Objects/hashes would probably make this problem easier, comparing a number to each key of a given set

Write out a few lines of initial pseudocode: (mid-level design, this should be short, and not be real code!)

fn toRoman(num):
  if (num == 0) return ""
  let numerals = {
    M: 1000
    CM: 900
    D:  500
    CD: 400
    // and so on
  }
  foreach ([key, value] of numerals):
    if (num - value > 0):
      return key + toRoman(num - value)

What do you think the Big O complexity of your algorithm is? (time complexity and space complexity)

The time complexity seems to be near O(n), because for each additional digit you must go through the same loop again. The space complexity I believe to be nX, because the numerals hash must be defined every loop through.