Integer To Roman InterviewBit Solution

Problem: Integer To Roman

Problem Description:

Given an integer A, convert it to a roman numeral, and return a string corresponding to its roman numeral version.

Input Format

The only argument given is integer A. 

Output Format

Return a string denoting roman numeral version of A. 

Constraints

1 <= A <= 3999 

For Example

Input 1:
    A = 5
Output 1:
    "V"

Input 2:
    A = 14
Output 2:
    "XIV"

Solution Approach:

The approach to this problem is quite straightforward, you just need to understand how Roman Numeral Systems is assigned to a number.

Time Complexity:

When you will see the solution you will realize that, in the first while loop, we keep decreasing the number by 1000 until it becomes less than 1000.

Once it is less than 1000, then the number of operations is more or less the same for any input, so we can consider the time complexity for the rest of the while loops as constant.

Now the problem comes with the first while loop, so the number of times it runs depends on input number N, for example:

For N < 1000, No. of operation = 0
For N < 2000, No. of operation = 1
For N < 3000, No. of operation = 2

So time complexity would be O(N/1000), so it should be O(N) for very large N.

Solution in C++: