Leetcode 12: Integer to Roman

1. Problem Statement (Simple Explanation):

You are given an integer num in the range: 1≤num≤3999

You must convert it to its Roman numeral representation.

Roman numerals use these symbols:

Roman Numeral Rules (Relevant to This Problem):

Additive notation:
Symbols are added from largest to smallest:

III = 3
VIII = 5 + 3 = 8
XXVII = 10 + 10 + 5 + 1 + 1 = 27

Subtractive notation (4s and 9s):
Used only in specific cases to avoid 4 in a row:

IV = 4 (5 − 1)
IX = 9 (10 − 1)
XL = 40 (50 − 10)
XC = 90 (100 − 10)
CD = 400 (500 − 100)
CM = 900 (1000 − 100)

Repetition constraints:

I, X, C, M can repeat at most 3 times in a row (e.g., III, XXX, CCC, MMM).
V, L, D are never repeated (you use subtractive forms instead of 4 repetitions).

Goal: Convert num to the shortest valid Roman numeral using these rules.

2. Examples:

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Breakdown:

3000 → MMM
700 → DCC (500 + 100 + 100)
40 → XL (50 − 10)
9 → IX (10 − 1)

Final: "MMM" + "DCC" + "XL" + "IX" = "MMMDCCXLIX"

Example 2:

Input: num = 58

Output: "LVIII"

Breakdown:

50 → L
8 → VIII (5 + 3)

Final: "L" + "VIII" = "LVIII"

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Breakdown:

1000 → M
900 → CM (1000 − 100)
90 → XC (100 − 10)
4 → IV (5 − 1)

Final: "M" + "CM" + "XC" + "IV" = "MCMXCIV"

3. Approach – Greedy Conversion with Value Table:

This is the standard, simple, and optimal solution.

Intuition:

We can think of Roman conversion like repeatedly subtracting the largest possible Roman value from num, appending its symbol, until num becomes 0.

To handle subtractive cases properly (4s and 9s), we just include them explicitly in our mapping.

We define two arrays (parallel):

values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

symbols = [ "M", "CM","D", "CD","C", "XC","L", "XL","X", "IX","V","IV","I"]

Then:

For each index i from 0 to 12:

While num >= values[i]:

Append symbols[i] to result.
Subtract values[i] from num.

Because we go from largest to smallest, we naturally:

Use subtractive pairs (CM, CD, etc.) when needed.
Avoid illegal forms (like IIII or VV).

Constraints are small enough that this O(1)-ish method is perfect.

Pseudo-code (Greedy):

Complexity:

values array has fixed size 13, and num is at most 3999.

Time: O(1) in practice (bounded by small constant).
Space: O(1) extra (excluding output string).

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code:

<<<PREV

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog