Given a Roman numeral, the task is to find its corresponding decimal value.
Example :
Input: IX
Output: 9
Explanation: IX is a Roman symbol which represents 9
Input: XL
Output: 40
Explanation: XL is a Roman symbol which represents 40
Input: MCMIV
Output: 1904
Explanation: M is a thousand, CM is nine hundred and IV is four
Roman numerals are based on the following symbols.
SYMBOL VALUE
I 1
IV 4
V 5
IX 9
X 10
XL 40
L 50
XC 90
C 100
CD 400
D 500
CM 900
M 1000
Approach: A number in Roman Numerals is a string of these symbols written in descending order(e.g. M’s first, followed by D’s, etc.). However, in a few specific cases, to avoid four characters being repeated in succession(such as IIII or XXXX), subtractive notation is often used as follows:
- I placed before V or X indicates one less, so four is IV (one less than 5) and 9 is IX (one less than 10).
- X placed before L or C indicates ten less, so forty is XL (10 less than 50) and 90 is XC (ten less than a hundred).
- C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand).
Algorithm to convert Roman Numerals to Integer Number:
- Split the Roman Numeral string into Roman Symbols (character).
- Convert each symbol of Roman Numerals into the value it represents.
- Take symbol one by one from starting from index 0:
- If current value of symbol is greater than or equal to the value of next symbol, then add this value to the running total.
- else subtract this value by adding the value of next symbol to the running total.
Following is the implementation of the above algorithm:
C++
#include <bits/stdc++.h>
using namespace std;
int value( char r)
{
if (r == 'I' )
return 1;
if (r == 'V' )
return 5;
if (r == 'X' )
return 10;
if (r == 'L' )
return 50;
if (r == 'C' )
return 100;
if (r == 'D' )
return 500;
if (r == 'M' )
return 1000;
return -1;
}
int romanToDecimal(string& str)
{
int res = 0;
for ( int i = 0; i < str.length(); i++) {
int s1 = value(str[i]);
if (i + 1 < str.length()) {
int s2 = value(str[i + 1]);
if (s1 >= s2) {
res = res + s1;
}
else {
res = res + s2 - s1;
i++;
}
}
else {
res = res + s1;
}
}
return res;
}
int main()
{
string str = "MCMIV" ;
cout << "Integer form of Roman Numeral is "
<< romanToDecimal(str) << endl;
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
int value( char r)
{
if (r == 'I' )
return 1;
if (r == 'V' )
return 5;
if (r == 'X' )
return 10;
if (r == 'L' )
return 50;
if (r == 'C' )
return 100;
if (r == 'D' )
return 500;
if (r == 'M' )
return 1000;
return -1;
}
int romanToDecimal( char str[])
{
int res = 0;
for ( int i = 0; i < strlen (str); i++)
{
int s1 = value(str[i]);
if (i + 1 < strlen (str))
{
int s2 = value(str[i + 1]);
if (s1 >= s2)
{
res = res + s1;
}
else
{
res = res + s2 - s1;
i++;
}
}
else {
res = res + s1;
}
}
return res;
}
int main()
{
char str[10] = "MCMIV" ;
printf ( "Integer form of Roman Numeral is %d" ,romanToDecimal(str));
return 0;
}
|
Java
import java.util.*;
public class RomanToNumber {
int value( char r)
{
if (r == 'I' )
return 1 ;
if (r == 'V' )
return 5 ;
if (r == 'X' )
return 10 ;
if (r == 'L' )
return 50 ;
if (r == 'C' )
return 100 ;
if (r == 'D' )
return 500 ;
if (r == 'M' )
return 1000 ;
return - 1 ;
}
int romanToDecimal(String str)
{
int res = 0 ;
for ( int i = 0 ; i < str.length(); i++) {
int s1 = value(str.charAt(i));
if (i + 1 < str.length()) {
int s2 = value(str.charAt(i + 1 ));
if (s1 >= s2) {
res = res + s1;
}
else {
res = res + s2 - s1;
i++;
}
}
else {
res = res + s1;
}
}
return res;
}
public static void main(String args[])
{
RomanToNumber ob = new RomanToNumber();
String str = "MCMIV" ;
System.out.println( "Integer form of Roman Numeral"
+ " is "
+ ob.romanToDecimal(str));
}
}
|
Python
def value(r):
if (r = = 'I' ):
return 1
if (r = = 'V' ):
return 5
if (r = = 'X' ):
return 10
if (r = = 'L' ):
return 50
if (r = = 'C' ):
return 100
if (r = = 'D' ):
return 500
if (r = = 'M' ):
return 1000
return - 1
def romanToDecimal( str ):
res = 0
i = 0
while (i < len ( str )):
s1 = value( str [i])
if (i + 1 < len ( str )):
s2 = value( str [i + 1 ])
if (s1 > = s2):
res = res + s1
i = i + 1
else :
res = res + s2 - s1
i = i + 2
else :
res = res + s1
i = i + 1
return res
print ( "Integer form of Roman Numeral is" ),
print (romanToDecimal( "MCMIV" ))
|
C#
using System;
class GFG {
public virtual int value( char r)
{
if (r == 'I' )
return 1;
if (r == 'V' )
return 5;
if (r == 'X' )
return 10;
if (r == 'L' )
return 50;
if (r == 'C' )
return 100;
if (r == 'D' )
return 500;
if (r == 'M' )
return 1000;
return -1;
}
public virtual int romanToDecimal( string str)
{
int res = 0;
for ( int i = 0; i < str.Length; i++) {
int s1 = value(str[i]);
if (i + 1 < str.Length) {
int s2 = value(str[i + 1]);
if (s1 >= s2) {
res = res + s1;
}
else {
res = res + s2 - s1;
i++;
}
}
else {
res = res + s1;
i++;
}
}
return res;
}
public static void Main( string [] args)
{
GFG ob = new GFG();
string str = "MCMIV" ;
Console.WriteLine( "Integer form of Roman Numeral"
+ " is "
+ ob.romanToDecimal(str));
}
}
|
Javascript
<script>
function value(r) {
if (r == 'I' )
return 1;
if (r == 'V' )
return 5;
if (r == 'X' )
return 10;
if (r == 'L' )
return 50;
if (r == 'C' )
return 100;
if (r == 'D' )
return 500;
if (r == 'M' )
return 1000;
return -1;
}
function romanToDecimal( str)
{
var res = 0;
for (i = 0; i < str.length; i++)
{
var s1 = value(str.charAt(i));
if (i + 1 < str.length) {
var s2 = value(str.charAt(i + 1));
if (s1 >= s2) {
res = res + s1;
}
else
{
res = res + s2 - s1;
i++;
}
} else {
res = res + s1;
}
}
return res;
}
var str = "MCMIV" ;
document.write( "Integer form of Roman Numeral"
+ " is " + romanToDecimal(str));
</script>
|
PHP
<?php
function value( $r )
{
if ( $r == 'I' )
return 1;
if ( $r == 'V' )
return 5;
if ( $r == 'X' )
return 10;
if ( $r == 'L' )
return 50;
if ( $r == 'C' )
return 100;
if ( $r == 'D' )
return 500;
if ( $r == 'M' )
return 1000;
return -1;
}
function romanToDecimal(& $str )
{
$res = 0;
for ( $i = 0; $i < strlen ( $str ); $i ++)
{
$s1 = value( $str [ $i ]);
if ( $i +1 < strlen ( $str ))
{
$s2 = value( $str [ $i + 1]);
if ( $s1 >= $s2 )
{
$res = $res + $s1 ;
}
else
{
$res = $res + $s2 - $s1 ;
$i ++;
}
}
else
{
$res = $res + $s1 ;
$i ++;
}
}
return $res ;
}
$str = "MCMIV" ;
echo "Integer form of Roman Numeral is " ,
romanToDecimal( $str ), "\n" ;
?>
|
Output
Integer form of Roman Numeral is 1904
Complexity Analysis:
- Time Complexity: O(n), where n is the length of the string.
Only one traversal of the string is required.
- Auxiliary Space: O(1), As no extra space is required.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!