Integer to Roman

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

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.

Integer to Roman

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).

Space Complexity

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

Translate ยป