Integer to Roman  

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg Microsoft Oracle
Math String

Integer to Roman conversion. We have given a number N and we need to print the Roman number of N. Roman numbers are represented by the use of {I, V, X, L, C, D, M} values. Let’s see some examples for good understanding.

Input Format  

Only a single line containing integer value N.

Output Format  

Print the result in a string format. In another way, we say that print only one line containing the Roman Number of N.

Constraints  

  • 1<=N<=3999.
Example Input-1:
47
Example Output-1:
XLVII
Example Input-2:
957
Example Output-2:
CMLVII

Explanation For Integer to Roman  

We find the roman number for a given number by the use of some precalculated values. We store the number and its roman number in a vector of pair<int, string>. Here is the list of some precalculated numbers which we use in the calculation of other numbers.

Please click Like if you loved this article?

Integer to RomanPin

When we find the Roman number for any number then we need to just find the count how many times we use which number to represent that number into roman values. Below is the algorithm which we follow to find the solution.

Algorithm For Integer to Roman  

Algorithm:
Step:1 Set sz as the size of vector(sz=v.size()) and string ans as empty(ans="").
Step:2 Find the value of count which we get when we divide the number(N) by value store in vector v[sz-1].first.
Step:3 Add the roman value of number count times which is precalculated in vector v[sz-1].second.
Step:4 Update the values(sz=sz-1 and n=n%(v[sz-1].first)).
Step:5 Repeat the step 2-4 while N is greater than 0.

Implementation For Integer to Roman  

/*C++ Implementation of Integer to Roman conversion Problem*/ 
#include<bits/stdc++.h>
using namespace std;
/*function to add the precalcuated values in vector.*/
void set_precalculated(vector<pair<int,string>>&v)
{
    v.push_back({1,"I"});
    v.push_back({4,"IV"});
    v.push_back({5,"V"});
    v.push_back({9,"IX"});
    v.push_back({10,"X"});
    v.push_back({40,"XL"});
    v.push_back({50,"L"});
    v.push_back({90,"XC"});
    v.push_back({100,"C"});
    v.push_back({400,"CD"});
    v.push_back({500,"D"});
    v.push_back({900,"CM"});
    v.push_back({1000,"M"});
}
int main() 
{ 
    int n;
    /*take N as input*/
    cin>>n;
    /*create a vector to store the precalculated roman values for some numbers(base numbers).*/
    vector<pair<int,string>> v;
    /*store the values*/
    set_precalculated(v);
    /*string which containg the final answer.*/
    string ans="";
    /*size of the vector*/
    int sz=v.size();
    /*repeat while N greter than 0.*/
    while(n>0&&sz>=0)
    {
        /*turn store the value which means we need to add v[sz-1].second turn number of times.*/
        int turn=n/(v[sz-1].first);
        /*update the value of N.*/
        n=n%(v[sz-1].first);
        /*add to the answer.*/
        for(int k=0;k<turn;k++)
        {
            ans+=(v[sz-1].second);
        }
        /*move to the next lowest precalculated number in vector*/
        sz--;
    }
    cout<<ans<<endl;
    return 0; 
}
1232
MCCXXXII

Time Complexity  

O(1) because the time taken for finding the roman number is constant O(1).

See also
Print a Binary Tree in Vertical Order

Space Complexity  

O(1) because we don’t create any extra space here to perform the implementation or operations.

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh