12. Integer to Roman

 

Converting Integers to Roman Numerals in JavaScript

Introduction

Roman numerals are an ancient system of writing numbers that dates back to the Roman Empire. They are still used today in various contexts, such as in clock faces, book chapters, and event names. Converting integers to Roman numerals is a common problem in computer science and often appears in coding interviews and competitive programming. In this blog post, we'll explore an efficient solution using JavaScript. We'll break down the approach, understand the underlying logic, and analyze the complexity of our solution.

Problem Statement

Given an integer, convert it to a Roman numeral. Roman numerals are represented by the symbols: I, V, X, L, C, D, and M.

Intuition

To convert an integer to a Roman numeral, we need to map the largest possible Roman numeral value to the integer and subtract that value repeatedly until we reach zero. By handling the values in descending order, we ensure that the resulting Roman numeral string is correct.

Approach

Our approach involves three main steps:

  1. Map Roman Numerals to Values:

    • Create a Map object symbolList that stores pairs of integers and their corresponding Roman numeral symbols in descending order.

  2. Initialize Result:

    • Initialize an empty string result which will store the final Roman numeral.

  3. Iterate Over Symbol List:

    • Iterate over each pair [val, sym] in the symbolList using a for...of loop.

    • For each pair, calculate how many times val can fit into num using Math.floor(num / val).

    • Append the Roman numeral symbol sym to result the calculated number of times using sym.repeat(count).

    • Update num by subtracting the total value added to result (count * val).

LeetCode Solution

Here's the complete JavaScript solution for the problem:

javascript
var intToRoman = function(num) {
    const symbolList = new Map([
        [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([val, sym] of symbolList) {
        const count = Math.floor(num / val);
        result += sym.repeat(count);
        num -= count * val;
    }
    return result;
};

Example

Let's walk through an example to understand how the code works:

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

In this example, the integer 1994 is converted to the Roman numeral "MCMXCIV".

Complexity Analysis

Time Complexity: O(1)

  • The time complexity is O(1) because the number of iterations in the loop is fixed and does not depend on the input size. The maximum number of iterations is 13, corresponding to the 13 pairs in the symbolList.

Space Complexity: O(1)

  • The space complexity is O(1) because the space used by the result string and the symbolList map is constant and does not depend on the input size.

Conclusion

This solution efficiently converts integers to Roman numerals by leveraging a fixed mapping of values to symbols and iterating through them in descending order. This approach ensures that the solution is both time-efficient and space-efficient, making it suitable for a wide range of input sizes.

Feel free to try out this solution in your projects or coding challenges. If you have any questions or suggestions, feel free to leave a comment. Happy coding!

For a detailed explanation and to see the complete solution, check out my Integer to Roman - LeetCode .

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more