Integer to Roman Palantir Python Interview Question

Before you solve this question, make sure to solve the easier warmup problem Roman to Integer, where you need to write a function that converts Roman numerals to integers.

In this problem, we're going the opposite direction – turning an integer into roman numerals. To refresh your memory, these seven different symbols represent Roman numerals with the following values:

Roman numerals are formed by converting decimal place values from highest to lowest. When converting an integer to a Roman numeral, follow these rules:

1. For numbers that don’t start with 4 or 9: Pick the symbol with the largest value that can be subtracted from the number. Append that symbol to the result, subtract its value, and repeat the process with the remaining number.

2. For numbers that start with 4 or 9: Use a subtractive form. This means you write one smaller symbol before a larger one. For example:

   • 4 is written as "IV" (1 less than 5),
   • 9 is written as "IX" (1 less than 10),
   • 40 is written as "XL" (10 less than 50),
   • 90 is written as "XC" (10 less than 100),
   • 400 is written as "CD" (100 less than 500),
   • 900 is written as "CM" (100 less than 1000).

3. Symbols can be repeated up to three times for powers of 10: Only the symbols for 1 (I), 10 (X), 100 (C), and 1000 (M) can be repeated consecutively, up to three times, to represent multiples of those values. Symbols like 5 (V), 50 (L), and 500 (D) cannot be repeated. If you need to append a symbol four times, use the subtractive form instead (like "IV" for 4).

Given an integer less than 4000, return the Roman numeral representation of that number.

Examples:

Example 1:

Input: $num = 30$

Output: "XXX"

Explanation:

• 30 = XXX, where each X represents 10.
  Don’t worry, this is perfectly safe for work—just three Roman tens, nothing more!

Example 2:

Input: $num = 69$

Output: "LXIX"

Explanation:

• 69 is represented as LXIX: L = 50, X = 10, IX = 9.
• Combining these gives us 50 + 10 + 9 = 69. Nice.

Approach 1

Let’s focus on the information in the question.

1. If the value does not start with 4 or 9, select the symbol of the maximum value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
2. If the value starts with 4 or 9, use the subtractive form representing one symbol subtracted from the following symbol. For example, 4 is 1 (I) less than 5 (V): IV, and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD), and 900 (CM).
3. Only powers of 10 (I, X, C, M) can be appended consecutively, at most 3 times, to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times, use the subtractive form.

The first one is pretty straightforward. If it doesn't start with 4 or 9, we will just subtract the maximum value that we can subtract from the number and append the symbol. Instead of subtracting, you can also use modulo; the result of the subtraction of the maximum number and the modulo of the number with the maximum number is the same. For example, for 56, the maximum number we can subtract is 50, and the result after subtraction is 6. Also, 56 mod 50 is 6, so you can use either.

The second one is no different from the first one; it is just that we have other numbers than the usual ones (I, V, X, L, C, D, M). You will do the same for the cases when two numbers are interpreted together. For example, for 46, the maximum number that we can subtract is 40, but 40 is not in the usual ones (single characters), so we will be including the combined ones (IV, IX, XL, XC, CD, CM) into consideration.

In the third case, you may be worried that you will append a single character more than 3 times, but if you follow the other steps correctly, here is how we will handle how many times we will add a single character:

1. We will start from the maximum number (1000).
2. We will divide (integer division, since we are looking for the number of times we will append a single character) the number by the current maximum. If the result is 0, it means the current maximum is greater than the number itself, so we will move to smaller maximum numbers. If the result is greater than 0, we will look up the Roman numeral representation of the current maximum number and append it to our answer the resulting number of times.
3. We will update the number either by subtracting the current maximum number times the result of the division or using modulo.

Here is the code to do that:

Optimized Approach

What we have been doing so far was following the steps listed in the question, but if we try to simplify it, what if we map the value of each digit? For example, for the thousands digit, we map values for 1000, 2000, and 3000 (since the number is always less than 4000). For the hundreds digit, we will map values for 100, 200, 300, ..., 900. For the tens digit, we will map 10, 20, 30, ..., 90, and for the ones place, we will store values of 1, 2, 3, ..., 9. Here are the Roman numerals for each digit:

Finally, we will extract each digit, starting from the thousands to the ones. We can achieve this using integer division and modulo operations:

• Thousands place:
  • Perform integer division by 1000: gives 1.
• Hundreds place:
  • First, remove the thousands digit using modulo: results in 234.
  • Then, perform integer division by 100: gives 2.
• Tens place:
  • Remove both the thousands and hundreds digits using modulo: gives 34.
  • Then, perform integer division by 10: gives 3.
• Ones place:
  • Finally, remove the previous digits using modulo: gives 4.

To make it simpler, let's define four different arrays for each digit and then place the value of each in its corresponding index. For example, the Roman numeral value of 700 will be placed at the 7th index of the hundreds digit, and 800 will be at the 8th. 50 will be at the 5th index of the tens digit. Each of the digits will have an empty string at the 0th index since it is possible that a number may have a 0 at some digits.

Here is the code: