# Solution by awice

• #### 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.

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