modalsoul’s blog

これは“失敗”と呼べるかもしれないが、ぼくは“学習体験”と呼びたい

LeetCode 12. Integer to Roman

LeetCode Problem No.12.

No.11 is here.

modalsoul.hatenablog.com

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1

Input: 3
Output: "III"

Example 2

Input: 4
Output: "IV"

Example 3

Input: 9
Output: "IX"

Example 4

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Code

object Solution {
  def intToRoman(num: Int): String = {
    def toRoman(i:String, v:String, x:String, n:Int) = {
      if(n == 4) i+v else if(n == 9) i+x else if(n < 4) i*n else v + (i * (n%5))
    }
    val i = toRoman("I", "V", "X", num%10)
    val x = toRoman("X", "L", "C", num%100/10)
    val c = toRoman("C", "D", "M", num%1000/100)
    val m = "M" * (num%10000/1000)
    m+c+x+i
  }
}

Methods

D: 1, 10, 100
I: D
V: 5*D
X: 10*D
  • In case n < 4, I by n
  • In case n = 4, V
  • In case n > 4, V and I by n%5
  • In case n = 9, IX

Results

Runtime: 480 ms, faster than 76.19% of Scala online submissions for Integer to Roman. Memory Usage: 49 MB, less than 100.00% of Scala online submissions for Integer to Roman.