Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
Integer to Roman is a popular LeetCode coding question asked at many tech companies including Amazon, Google, Apple, Bloomberg, and Adobe. This algorithm question is a math based question involving the use of the division and modulus operators.
To solve this problem, we first must define all roman numerals that we could potentially have in our result. Roman numerals do have some odd edge cases where occasionally we must perform subtraction from the roman numeral on the right to the roman numeral on the left. Once we have all of our conversions ranging from 1000 to 1, we then can convert any integer to a roman numeral.
We loop over all of our numerals and divide the number from our input number. The result from division is the number of symbols we must add to our result for that specific conversion. Once we append the roman numeral(s) to our result, we then utilize the modulus operator to chop off the most significant digit from our input number. We do this for each conversion until our input number becomes zero.
The time complexity of our solution is going to be big oh of N where N is the number of roman numeral characters we have in our result. We use the repeat function in Java to generate all of the characters. Our space complexity is constant since we do not initialize any extra memory in the algorithm.