Integer to Roman

Array, Iterative Approach

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.

• X can be placed before L (50) and C (100) to make 40 and 90.

• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= num <= 3999

Solutions

The problem is to convert an integer to a Roman numeral. The solution involves a process of repeatedly subtracting the largest possible Roman numeral value from the input number and appending the corresponding Roman numeral to the result. This process continues until the input number has been reduced to zero. The final result is the Roman numeral representation of the original input number. The solution also includes a validation step to ensure that the input number is within the valid range for Roman numerals (1 to 3999). If the input number is outside this range, the function returns an empty string.

Approach - Brute Force Technique

Checks each numeral in the dictionary for every subtraction until the number becomes zero.

Steps

1. Dictionary Initialization: A dictionary romanLatters is initialized with integer values as keys and their corresponding Roman numerals as values. The dictionary is sorted in descending order of keys.

2. Input Validation: The IsValidInput function checks if the input number num is within the valid range (1 to 3999). If the input number is outside this range, the function returns false, and the IntToRoman function will return an empty string.

3. Roman Numeral Conversion: The IntToRoman function converts the input number to a Roman numeral. It initializes an empty string result to store the Roman numeral.

4. Iteration Over Dictionary: The function enters a while loop that continues as long as the current number num is not zero. Inside the while loop, it iterates over each item in the romanLatters dictionary.

5. Subtraction and Appending: For each dictionary item, it checks if the current number num is greater than or equal to the key of the item. If it is, it appends the value of the item (the Roman letter) to result and subtracts the key of the item (the Roman numeral) from num. Then it breaks the foreach loop and goes back to the while loop.

6. Next Dictionary Item: If num is not zero and is less than the key of the current dictionary item, the function moves to the next item in the dictionary and repeats the process.

7. Completion: The function continues this process until num becomes zero. At this point, all the Roman numerals that make up the input number have been appended to result.

8. Return Result: Finally, the function returns the Roman numeral as a string.

public class Solution {
    public Dictionary<int, string> romanLatters = new Dictionary<int, string>()
    {
        {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"}
    };
    public string IntToRoman(int num)
    {
        if (!IsValidInput(num))
            return string.Empty;

        string result = string.Empty;
        while (num != 0)
        {

            foreach (var item in romanLatters)
            {
                if (num>=item.Key)
                {
                    result += item.Value;
                    num = num - item.Key;
                    break;

                }
            }
        }
        return result;
    }

    private bool IsValidInput(int num)
    {

        return 1 <= num && num <= 3999;
    }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the number of Roman numerals is fixed (13 numerals), and the maximum possible number is also fixed (3999). Therefore, the number of iterations does not grow with the size of the input number, making the time complexity constant.

Space Complexity: The space complexity is also O(1). The space used by the program does not grow with the size of the input number. The dictionary of Roman numerals uses a constant amount of space, and the string result will at most hold the Roman numeral equivalent of the number 3999, which is a fixed length string.

Please note that this analysis assumes that dictionary lookups, string concatenation, and integer comparisons/subtractions can be done in constant time.

Approach - Iterative Technique

Iterates over the dictionary and for each key-value pair, it performs a loop operation until the number is less than the key.

Steps

1. Dictionary Initialization: A dictionary romanLatters is initialized with integer values as keys and their corresponding Roman numerals as values. The dictionary is sorted in descending order of keys.

2. Input Validation: The IsValidInput function checks if the input number num is within the valid range (1 to 3999). If the input number is outside this range, the function returns false, and the IntToRoman function will return an empty string.

3. Roman Numeral Conversion: The IntToRoman function converts the input number to a Roman numeral. It initializes an empty StringBuilder object result to store the Roman numeral.

4. Iteration Over Dictionary: The function iterates over each item in the romanLatters dictionary. For each item, it enters a while loop that continues as long as the current number num is greater than or equal to the key of the current dictionary item.

5. Subtraction and Appending: Inside the while loop, the function appends the value of the current dictionary item (the Roman letter) to result and subtracts the key of the current dictionary item (the Roman numeral) from num. This process continues until num becomes less than the key of the current dictionary item.

6. Next Dictionary Item: Once num becomes less than the key of the current dictionary item, the function moves to the next item in the dictionary and repeats the process.

7. Completion: The function continues this process until num becomes zero. At this point, all the Roman numerals that make up the input number have been appended to result.

8. Return Result: Finally, the function returns the Roman numeral as a string by calling the ToString method on result.

public class Solution {
    public Dictionary<int, string> romanLatters = new Dictionary<int, string>()
    {
        {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"}
    };
    public string IntToRoman(int num)
    {
        if (!IsValidInput(num))
            return string.Empty;

        StringBuilder result = new StringBuilder();
        foreach (var item in romanLatters)
        {
            while (num >= item.Key)
            {
                result.Append(item.Value);
                num -= item.Key;
            }
        }
        return result.ToString();
    }

    private bool IsValidInput(int num)
    {
        return 1 <= num && num <= 3999;
    }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the number of Roman numerals is fixed (13 numerals), and the maximum possible number is also fixed (3999). Therefore, the number of iterations does not grow with the size of the input number, making the time complexity constant.

Space Complexity: The space complexity is also O(1). The space used by the program does not grow with the size of the input number. The dictionary of Roman numerals uses a constant amount of space, and the StringBuilder object result will at most hold the Roman numeral equivalent of the number 3999, which is a fixed length string.

Please note that this analysis assumes that dictionary lookups, StringBuilder append operations, and integer comparisons/subtractions can be done in constant time.