Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

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.

PreviousUnique Integers That Sum Up To 0NextFlatten

Last updated 1 year ago