12.Integer to Roman

Tags: [roman], [num], [tuple], [trick], [greedy]

Link: https://leetcode.com/problems/integer-to-roman/\#/description

Given an integer, convert it to a roman numeral.

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

Solution: Trick

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num <= 0:
            raise ValueError('the input is invalid')

        romans = [
            (1000, 'M'),
            (900, 'CM'),
            (500, 'D'),
            (400, 'CD'),
            (100, 'C'),
            (90, 'XC'),
            (50, 'L'),
            (40, 'XL'),
            (10, 'X'),
            (9, 'IX'),
            (5, 'V'),
            (4, 'IV'),
            (1, 'I')
        ]

        result = []
        for r in romans:
            base, roman = r
            if num < base:
                continue

            for _ in xrange(num / base):
                result.append(roman)

            num %= base

        return ''.join(result)

Revelation:

• We need to list all special romans, including 900, 400, 90, 9, 4.

Note:

• Time complexity = O(1), because the number of elements of romans is constant.
• Space complexity = O(1), not including the result space.