roman_numeral_recursion.md

Instructions

1. Fork this gist, then "edit" the gist
2. Fill out the questions below
3. Click the "Add file" button and add your source code to the gist
4. Submit by the due time as instructed in Zoom

Do not publish your code on a public repl.it or repo or other public means.

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 converts any integer smaller than 4000 into roman numerals, using the most efficient roman numeral.

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

• I'm assuming I'm going to need to write a function that breaks down whatever number that is passed down into the biggest possible chunks, starting with 1000, 500, 100 and so on down to 1.
• I assume that I'll need to subtract chunks out of my number in order for the recursive function to work properly.
• I assume that my base case will be once the number = 0 I will return the array number.
• I assume that as I subtract the big chunks out of the number I'll push a letter into my roman numeral array that I will then join once the number is at 0.
• I assume that I only need to be able to calculate roman numeral values for arguments between 0 - 4000.

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

I articulated some of my initial thoughts in the assumptions section, but to reiterate, I will be writing some conditional logic that will check to see if the number is > 0 for my recursive case that will subtract some amount out of the given number until it reaches 0. Each time a number is subtracted out of the total and converted into a Roman Numeral, I will push that roman numeral into the answer array. Once I reach my base case I will join the array and return the roman numeral all smashed together.

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?

I think a combination of an answer array converted into a string will be involved. Otherwise I think I should be fine just using some math conditional logic. Let's get to the pseudocoding!

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

// set a variable of romanNumeral = to empty array where we will push our roman numerals when they are found // Write base case logic where if number === 0, we will join the roman numeral index values and return them // Write the recursive case where we check to see if the number is greater than 1000. If it is, we want to push an 'M' into our romanNumeral array & subtract 1000 from our number, then call the recursive function again.
// Write a similar if else conditional for 500 which would translate to a 'D' and subtract 500. // Write a similar if else conditional for 100 which would translate to a 'C' and subtract 100. // Write a similar if else conditional for 50 which would translate to an 'L' and subtract 50. // Write a similar if else conditional for 10 which would translate to an 'X' and subtract 10. // Write a similar if else conditional for 5 which would translate to a 'V' and subtract 5.

I know that once I get the big chunks of code removed and converted I'm going to need to be able to calculate the smaller roman numeral numbers. I'm not sure if I'll need to have the benchmarks for 900, 400, 90, 40, 9 & 4 as those are all provided in the Roman Numeral equivalents you'll need to know section.

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

I believe it is O(1) because there are no nested functions, but each if/else block requires a check of a single value comparison.

JS Starter Code

function toRoman(num) {
  // your code goes here
}

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"

Ruby Starter Code

def to_roman(num)
  # your code goes here
end

puts to_roman(128)   # should return "CXXVIII"
puts to_roman(2000)  # should return "MM"
puts to_roman(2017)  # should return "MMXVII"
puts to_roman(1999)  # should return "MCMXCIX"

toRoman.js

function toRoman(number, roman) {
    if (roman === undefined) {
        var roman = []
    }

    if (number === 0) {
        return roman.join('')
    }

    if (number >= 1000) {
        roman.push('M')
        toRoman(number - 1000, roman)
    } else if (number >= 900) {
        roman.push('CM')
        toRoman(number - 900, roman)
    } else if (number >= 500) {
        roman.push('D')
        toRoman(number - 500, roman)
    } else if (number >= 400) {
        roman.push('CD')
        toRoman(number - 400, roman)
    } else if (number >= 100) {
        roman.push('C')
        toRoman(number - 100, roman)
    } else if (number >= 90) {
        roman.push('XC')
        toRoman(number - 90, roman)
    } else if (number >= 50) {
        roman.push('L')
        toRoman(number - 50, roman)
    } else if (number >= 40) {
        roman.push('XL')
        toRoman(number - 40, roman)
    } else if (number >= 10) {
        roman.push('X')
        toRoman(number - 10, roman)
    } else if (number >= 9) {
        roman.push('IX')
        toRoman(number - 9, roman)
    } else if (number >= 5) {
        roman.push('V')
        toRoman(number - 5, roman)
    } else if (number >= 4) {
        roman.push('IV')
        toRoman(number - 4, roman)
    } else if (number >= 1) {
        roman.push('I')
        toRoman(number - 1, roman)
    }
}


console.log(toRoman(128))
console.log(toRoman(2000))
console.log(toRoman(2017))
console.log(toRoman(1999))