LC-0012 Medium LeetCode

12. Integer to Roman

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Hash Table, Math, String

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Strings 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        numeral_map = {1: "I", 4: "IV", 5: "V", 9: "IX", \
                       10: "X", 40: "XL", 50: "L", 90: "XC", \
                       100: "C", 400: "CD", 500: "D", 900: "CM", \
                       1000: "M"}
        keyset, result = sorted(numeral_map.keys()), []

        while num > 0:
            for key in reversed(keyset):
                while num / key > 0:
                    num -= key
                    result += numeral_map[key]

        return "".join(result)

Solution from kamyu104/LeetCode-Solutions · MIT