CodingGyan

Integer to Roman Numeral

medium Number Problems

Problem

Read an integer from 1 to 3999 and print it as a Roman numeral. Roman numerals use the letters I (1), V (5), X (10), L (50), C (100), D (500) and M (1000). Special forms like IV (4) and IX (9) are used instead of repeating a letter four times.

Constraints

  • 1 <= n <= 3999

Examples

Input

1994

Output

MCMXCIV

Solutions

Best approachTime O(1)Space O(1)

A greedy method: always take the largest value that still fits. Adding the special values 900, 400, 90, 40, 9 and 4 to the table removes the need for special rules.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Convert an integer to a Roman numeral.
 * Input   : One integer from 1 to 3999.
 * Output  : The Roman numeral.
 * Approach: Go through a table of values from large to small.
 * Time    : O(1)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int number = new Scanner(System.in).nextInt();

        // Step 1: Two lists with the same order: the values and their Roman letters. Large values come first.
        // The list also has the special forms 900 (CM), 400 (CD), 90 (XC), 40 (XL), 9 (IX) and 4 (IV).
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        // Step 2: The result is empty at the start.
        StringBuilder result = new StringBuilder();

        // Step 3: Go through the table from the largest value to the smallest value.
        for (int index = 0; index < values.length; index++) {
            // Step 4: While the number is large enough, write the symbol and subtract its value. Example: 3000 -> M, M, M.
            while (number >= values[index]) {
                result.append(symbols[index]);
                number = number - values[index];
            }
        }

        // Step 5: Print the Roman numeral.
        System.out.println(result);
    }
}
Hints (2)
  1. Which Roman symbol is the largest one that fits into the number?
  2. Why do we add IV and IX to the table?

Try these next