Integer to Roman In C,CPP,JAVA,PYTHON,C#,JS

Spread the love

Table of Contents

Problem Statement: Integer to Roman

The task is to convert a given integer to its equivalent Roman numeral. Roman numerals are represented by seven symbols:

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

Roman numerals are usually written in descending order from left to right, but there are exceptions for certain combinations that represent numbers in a more compact form. For example:

IV = 4 (instead of IIII)
IX = 9 (instead of VIIII)
XC = 90 (instead of LXXXX)
CD = 400 (instead of CCCC)
CM = 900 (instead of DCCCC)

Example:

Input:

n = 58

Output:

"LVIII"

Input:

n = 1994

Output:

"MCMXCIV"

Approach:

Create a List of Roman Numerals and Their Values:
- Create a list of tuples where each tuple consists of a Roman numeral and its corresponding integer value in descending order:cssCopy code[(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
Iterate Through the List:
- Start with the largest value and check how many times it fits into the given integer.
- Append the corresponding Roman numeral to the result for each match.
- Subtract the matched value from the integer and continue with the next largest value.
Termination:
- Repeat the process until the integer becomes zero, at which point the result will be a valid Roman numeral.
Edge Case Handling:
- The input should be between 1 and 3999, as Roman numerals don’t have standard representations for values beyond this range.

Time Complexity:

Time Complexity: O(1)O(1)O(1), since there are a fixed number of Roman numeral values (13 in total).
Space Complexity: O(1)O(1)O(1), as the space used does not depend on the input size but on the fixed list of Roman numeral values.

Code Implementation

C Code:

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

void intToRoman(int num, char* result) {
    // List of Roman numerals and their corresponding values
    const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    const char* numerals[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
    int i = 0;
    result[0] = '\0';  // Initialize result as an empty string
    
    while (num > 0) {
        while (num >= values[i]) {
            strcat(result, numerals[i]);
            num -= values[i];
        }
        i++;
    }
}

int main() {
    int num = 1994;
    char result[20];
    
    intToRoman(num, result);
    printf("Roman numeral of %d is: %s\n", num, result);
    
    return 0;
}

C++ Code:

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

string intToRoman(int num) {
    vector<pair<int, string>> values = {
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
        {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"},
        {5, "V"}, {4, "IV"}, {1, "I"}
    };
    
    string result = "";
    
    for (auto& [value, numeral] : values) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }
    
    return result;
}

int main() {
    int num = 1994;
    cout << "Roman numeral of " << num << " is: " << intToRoman(num) << endl;
    return 0;
}

Java Code:

public class Solution {
    public String intToRoman(int num) {
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(romans[i]);
                num -= values[i];
            }
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int num = 1994;
        System.out.println("Roman numeral of " + num + " is: " + solution.intToRoman(num));
    }
}

Python Code:

def intToRoman(num: int) -> str:
    values = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
        (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
    ]
    
    result = []
    
    for value, numeral in values:
        while num >= value:
            result.append(numeral)
            num -= value
    
    return ''.join(result)

# Example Usage
num = 1994
print(f"Roman numeral of {num} is: {intToRoman(num)}")

C# Code:

using System;
using System.Text;

public class Solution {
    public string IntToRoman(int num) {
        var values = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        var numerals = new string[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < values.Length; i++) {
            while (num >= values[i]) {
                result.Append(numerals[i]);
                num -= values[i];
            }
        }
        
        return result.ToString();
    }

    public static void Main() {
        Solution solution = new Solution();
        int num = 1994;
        Console.WriteLine($"Roman numeral of {num} is: {solution.IntToRoman(num)}");
    }
}

JavaScript Code:

var intToRoman = function(num) {
    const values = [
        [1000, "M"], [900, "CM"], [500, "D"], [400, "CD"], [100, "C"], [90, "XC"],
        [50, "L"], [40, "XL"], [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"]
    ];
    
    let result = '';
    
    for (let [value, numeral] of values) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }
    
    return result;
};

console.log(intToRoman(1994));  // Output: "MCMXCIV"

Summary:

The algorithm works by greedily subtracting the largest possible Roman numeral from the integer at each step, appending the corresponding symbol to the result.
Time Complexity: O(1)O(1)O(1), since there are a fixed number of Roman numeral values.
Space Complexity: O(1)O(1)O(1), as we are only storing the result string, which has a constant upper bound in length for valid inputs (since the input is limited to 3999).