Convert Integer to Roman Numeral

Given a positive integer num, your task is to convert it into a Roman numeral as per the classical Roman numeral system.

• Roman numerals use combinations of letters from the Latin alphabet: I, V, X, L, C, D, and M.
• There are specific rules for combining symbols to represent numbers, including using subtraction (e.g., IV for 4, IX for 9).

Note: The input number will be a positive integer between 1 and 3999 (inclusive). If the input is outside this range or invalid (like 0 or negative), return an appropriate message or handle it gracefully.

Understanding the Problem

Roman numerals are a numeral system originating from ancient Rome. They use combinations of letters from the Latin alphabet to represent values. The basic symbols are:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

The goal is to convert an integer (between 1 and 3999) into its Roman numeral representation by applying a set of well-defined rules.

Step-by-Step Solution with Example

Step 1: Create the mapping

We start by preparing a list of Roman symbols along with their corresponding integer values. This list must be ordered from largest to smallest, and should also include the special subtractive forms like IV (4), IX (9), XL (40), etc.

Step 2: Pick an example

Let's say the number is 58. We will walk through converting this number step-by-step using our list of Roman numerals.

Step 3: Match the highest symbol

We find the largest Roman numeral value less than or equal to 58. This is L = 50. So we subtract 50 from 58, leaving us with 8. We also add 'L' to our result.

Step 4: Continue subtracting

Now we match the largest value ≤ 8. It is V = 5. Subtract 5 → we now have 3. Add 'V' to the result.

Step 5: Final subtractions

The remaining value is 3, which is represented by three I's. Add 'III' to the result.

Step 6: Final result for example

Combining all symbols we collected: L + V + III = LVIII. This is the Roman numeral representation of 58.

Step 7: General algorithm

1. Create a list of value-symbol pairs sorted in descending order.
2. Initialize an empty result string.
3. Iterate over the value-symbol list:
4. While the current value can be subtracted from the number:
5. Subtract it and append the corresponding symbol to the result.
6. Continue until the number becomes 0.

Example for 1994: Break it down as M (1000) + CM (900) + XC (90) + IV (4) → Result is MCMXCIV.

Edge Cases

• Zero or Negative Numbers: Roman numerals do not support 0 or negative values. Return an error or message like "Invalid input".
• Numbers above 3999: The standard Roman numeral system does not represent numbers above 3999. Again, return a clear message.
• Empty input or non-numeric input: Return "Invalid input" if input is null, empty, or not a number.

Finally

This problem teaches how to translate a number system based on values and subtractive combinations into code. By breaking the number from the highest Roman value down, we ensure a valid and readable representation. With proper checks for invalid cases and a clear mapping, this algorithm remains simple, efficient, and beginner-friendly.

1. Create two arrays: one for the integer values and one for corresponding Roman symbols, both sorted in descending order.
2. Initialize an empty string to hold the result.
3. Loop over the integer values array:
4. → While the input number is greater than or equal to the current integer value:
5. → Subtract that value and append the corresponding Roman symbol to the result.
6. Repeat until the number becomes 0.
7. Return the result string.

#include <stdio.h>
#include <string.h>

void intToRoman(int num, char *result) {
  int val[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  char *syms[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
  result[0] = '\0';
  for (int i = 0; i < 13; i++) {
    while (num >= val[i]) {
      strcat(result, syms[i]);
      num -= val[i];
    }
  }
}

int main() {
  char roman[100];
  intToRoman(1994, roman);
  printf("%s\n", roman);
  return 0;
}

#include <iostream>
#include <string>
using namespace std;

string intToRoman(int num) {
  int val[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  string syms[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
  string roman = "";
  for (int i = 0; i < 13; i++) {
    while (num >= val[i]) {
      roman += syms[i];
      num -= val[i];
    }
  }
  return roman;
}

int main() {
  cout << intToRoman(1994) << endl;
  return 0;
}

def int_to_roman(num):
    val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    roman = ""
    for i in range(len(val)):
        while num >= val[i]:
            roman += syms[i]
            num -= val[i]
    return roman

print(int_to_roman(1994))

public class RomanConverter {
  public static String intToRoman(int num) {
    int[] val = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder roman = new StringBuilder();
    for (int i = 0; i < val.length; i++) {
      while (num >= val[i]) {
        roman.append(syms[i]);
        num -= val[i];
      }
    }
    return roman.toString();
  }
  public static void main(String[] args) {
    System.out.println(intToRoman(1994));
  }
}

function intToRoman(num) {
  const val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
  let roman = "";
  for (let i = 0; i < val.length; i++) {
    while (num >= val[i]) {
      roman += syms[i];
      num -= val[i];
    }
  }
  return roman;
}

console.log(intToRoman(1994));

package main

import (
  "fmt"
)

func intToRoman(num int) string {
  val := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
  syms := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
  roman := ""
  for i := 0; i < len(val); i++ {
    for num >= val[i] {
      roman += syms[i]
      num -= val[i]
    }
  }
  return roman
}

func main() {
  fmt.Println(intToRoman(1994))
}

fn int_to_roman(mut num: i32) -> String {
    let val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    let mut roman = String::new();
    for i in 0..val.len() {
        while num >= val[i] {
            roman.push_str(syms[i]);
            num -= val[i];
        }
    }
    roman
}

fn main() {
    println!("{}", int_to_roman(1994));
}

fun intToRoman(num: Int): String {
    val valArr = arrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val symArr = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
    var n = num
    val roman = StringBuilder()
    for (i in valArr.indices) {
        while (n >= valArr[i]) {
            roman.append(symArr[i])
            n -= valArr[i]
        }
    }
    return roman.toString()
}

fun main() {
    println(intToRoman(1994))
}

func intToRoman(_ num: Int) -> String {
    let val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    let syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    var n = num
    var roman = ""
    for i in 0..<val.count {
        while n >= val[i] {
            roman += syms[i]
            n -= val[i]
        }
    }
    return roman
}

print(intToRoman(1994))

function intToRoman(num: number): string {
  const val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
  let roman = "";
  for (let i = 0; i < val.length; i++) {
    while (num >= val[i]) {
      roman += syms[i];
      num -= val[i];
    }
  }
  return roman;
}

console.log(intToRoman(1994));

Time complexity

Space complexity

O(1)

Only a few variables and fixed arrays are used. No additional memory scales with input.