LeetCode 12. Integer to Roman

Description

https://leetcode.com/problems/integer-to-roman/

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Explanation

The problem is about writing a function to convert an Arabic number to a Roman number.

We need to have some basic knowledge about Roman numerals.

Roman numerals, as used today, are based on seven symbols:

Symbol I V X L C D M
Value 1 5 10 50 100 500 1,000

Numbers are formed by combining symbols and adding the values. Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX), a subtractive notation is used: as in this table:

Number 4 9 40 90 400 900
Notation IV IX XL XC CD CM
  • I placed before V or X indicates one less, so four is IV (one less than five) and nine is IX (one less than ten)
  • X placed before L or C indicates ten less, so forty is XL (ten less than fifty) and ninety is XC (ten less than a hundred)
  • C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand)

We build two arrays with the same length to solve the problem. One is storing values; the other one is storing Roman characters. Two arrays should have the same number at same index positions.

We develop our algorithms based on Roman subtractive method. Every time we subtract a value from input number, we add related Roman character to the result string.

Video Tutorial

Java Solution

One thought

  1. @thegoodtecher I have a word extension problem in which I want to print list of characters along with its starting and end index if a char appears consecutively more than n number of times. For e.g. heeeelllo will return [[e,[1,4]],[l,[5,7]].e & l appears more than 3 times.

Leave a Reply

Your email address will not be published. Required fields are marked *