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.