Solution by awice


  • 0

    Approach #1: Repeated Subtraction [Accepted]

    Intuition

    If say, N = 1234, then the answer would be 'M' plus the answer for N = 234. Our idea is to write the number from left to right, using the largest available token.

    Algorithm

    We repeatedly remove the largest value represented by a token, and write that token in our answer. For example, if we have N = 25, we will write 'X', then 'X', then 'V', as our integer N moves from 25, to 15, and finally 5.

    However, for an integer like N = 9, the answer is 'IX', not 'VIIII' We can repair our initial idea by using not just tokens like 'M', 'D', 'C', 'L', 'X', 'V', 'I', but also tokens like 'CM', 'CD, 'XC', 'XL', 'IX', 'IV'.

    Python

    class Solution(object):
        def intToRoman(self, N):
            tokens = [('M', 1000), ('CM', 900), ('D', 500), ('CD', 400),
                      ('C', 100), ('XC', 90), ('L', 50), ('XL', 40),
                      ('X', 10), ('IX', 9), ('V', 5), ('IV', 4), ('I', 1)]
            ans = []
            while N > 0:
                for token, value in tokens:
                    while N >= value:
                        ans.append(token)
                        N -= value
            return "".join(ans)
    

    Complexity Analysis

    • Time Complexity: Let $$N$$ be the given number. In general, we will make at least $$N/1000$$ writes to our array, which is order $$O(N)$$. In our specific case of N < 4000, we will loop through our tokens array up to 13 times, and make no more than 15 writes, which has $$O(1)$$ complexity.

    • Space Complexity: As described above, for the general case, the final answer has $$O(N)$$ letters. As it is given that N < 4000, the answer never has more than 15 letters, which can be considered $$O(1)$$ space.


    Approach #2: Construction [Accepted]

    Intuition

    The answers for the thousands, hundreds, tens, and ones place can be independently added together.

    Algorithm

    By hand, we will compute the answer for N = 0, 1, 2, 3, ..., 9; for N = 0, 10, 20, 30, ..., 90, for N = 0, 100, 200, ..., 900, and for N = 0, 1000, 2000, 3000. At the end, we will concatenate these answers together.

    Python

    class Solution(object):
        def intToRoman(self, N):
            A = [["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
                 ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
                 ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
                 ["", "M", "MM", "MMM"]]
            return A[3][N//1000%10] + A[2][N//100%10] + A[1][N//10%10] + A[0][N%10]
    

    Complexity Analysis

    • Time Complexity: Let $$N$$ be the given number. We seek four strings and add them together in $$O(1)$$ time.

    • Space Complexity: We use a constant amount of space ($$O(1)$$) to hold the correct partial answers directly in our code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.