integer-to-roman-numeral.md

Requirements

Given a number, return the roman numeral.

Strategy

We're going back in time to the third century! Subtract the integer value of a roman numeral from the input value until the value is less than that the roman numeral value. Then move to the next roman numeral.

Justification of strategy

Roman numerals are just sums of particular integers. We want to find the sum created by the discrete number of integers provided by roman numerals. So we have to break the integer down, starting with our biggest building blocks. We only need to move to a smaller roman numeral if after dividing our input by the roman numeral there's a remainder. We handle the thousands, and then the hundreds, and finally the units. Once we find a value that is smaller or equal to our number, we will push the matching letter to our solution and subtract this value from our number.

Define test cases

• intToRoman(123) should return "CXXIII"
• intToRoman(949) should return "CMXLIX"
• intToRoman(3000) should return "MMM"

Implementation skeleton

• declare storage for resul string
• make a graph with two arrays, mapping an array of integers to an array of roman numerals such that an index will map the two as we iterate through the integers array.
• iterate over array of integers
  • while we can still use the current roman numeral to build our string
    • add the roman numeral to the result string
    • subtract the roman numeral's integer from the input value
• return the result string

Actual implementation

https://gist.github.com/PantherHawk/59bdf44393c3d276fb6eda93a864c7b4

Execute test cases

function assert(a, b) {
  return a === b ? 'SUCCESS' : 'FAILURE';
}

assert(intToRoman(123), "CXXIII");
assert(intToRoman(949), "CMXLIX");
assert(intToRoman(3000), "MMM");

Big-O Analysis

O(1), Constant Time.

Optimization (if applicable)