Instructions

Fork this gist, then "edit" the gist
Fill out the questions below
Click the "Add file" button and add your source code to the gist
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 takes in a number and returns a string of that numbers Roman Numeral in the most effecient way. So, for example, if you pass in 4, you should return IV, not IIII, as IV is more efficient. (Efficient being shorter).

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

Assuming that no numbers we're passing in will be larger than 4,000.

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

First thought, holy moly. Second thought, I need to get a stronger grasp on Roman Numerals. So, googling here I come. Also, hmmmm how do I make it recursive. First, need to figure out how to do one and then find a pattern to repeat in that solution.

How do Roman Numerals work? Well when a symbol appears after a larger (or equal) symbol it is added (AFTER LARGER IS ADDED)

Example: VI = V + I = 5 + 1 = 6
Example: LXX = L + X + X = 50 + 10 + 10 = 70

But if the symbol appears before a larger symbol it is subtracted

Example: IV = V − I = 5 − 1 = 4
Example: IX = X − I = 10 − 1 = 9

Also, don't use the same symbol more than three times in a row.

How would you identify the elements of this problem?

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

I could use objects to hold our known values and at the end I could use an array to push our final results into. Pros: Easy to keep values in an object and easy to push results into a final results array Cons: A lot of moving data around with how I'm thinking about things.

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

First, define our known roman numeral values in an object. Something like this...

let romanValues = {
  I: 1,
  V: 5,
  X: 10,
  L: 50,
  C: 100,
  D: 500,
  M: 1000
}

Next, break the number into thousands, hundreds, tens, and ones.

First, take the number and if it's greater than or equal to 1000, start by dividing by 1000. Take the quotient and multiply it by 1000 and save this value in an object. Then, take the remainder (modulo) and divide that by 100. Take the quotient and multiply it by 100 and save this value in an object. Then, take that remainder and divide by 10. Take the quotient and multiply it by 10 and save this value in an object. Then, take that remainder and divide by 1. Take the quotient and multiply by 1. Now we'll have an object that looks something like this if we started with the number 1984...

let values = {
  thousands = 1000,
  hundreds = 900,
  tens = 80,
  ones = 4
}

Now, we have to convert our values in the values object to roman numerals. (STILL NEED TO FIGURE THIS PART OUT). If we can save that into an object, we could take the Object.values(), interate through each element and push each element into a results array. Then, finally, we could take that results array and run array.toString(), split and join it to get our final answer.


RECURSION
//base case - stop when our modulo is 0

//recursive case - taking the remainder of the previous division and dividing by the next number. So starting by dividing by 1000, 100, 10, stopping when we get to 1.

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

Didn't get to a solution.

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"

michellekaplan7/roman_numeral_recursion.md

Select an option

No results found