Largest Roman Numeral possible by rearranging characters of a given string | C ++ implementation of the above approach ; Function to find decimal value of a roman character ; Function to convert string representing roman number to equivalent decimal value ; Stores the decimal value of the string S ; Stores the size of the S ; Update res ; Traverse the string ; Return res ; Function to convert decimal to equivalent roman numeral ; Stores the string ; Stores all the digit values of a roman digit ; Iterate while number is greater than 0 ; Return res ; Function to sort the string in descending order of values assigned to characters ; Function to find largest roman value possible by rearranging the characters of the string ; Stores all roman characters ; Traverse the string ; If X is not found ; Stores the decimal value of the roman number ; Find the roman value equivalent to the decimal value of N ; Return result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int charVal ( char c ) { if ( c == ' I ' ) return 1 ; if ( c == ' V ' ) return 5 ; if ( c == ' X ' ) return 10 ; if ( c == ' L ' ) return 50 ; if ( c == ' C ' ) return 100 ; if ( c == ' D ' ) return 500 ; if ( c == ' M ' ) return 1000 ; return -1 ; } int romanToDec ( string S ) { int res = 0 ; int n = S . size ( ) ; res = charVal ( S [ n - 1 ] ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( charVal ( S [ i ] ) < charVal ( S [ i + 1 ] ) ) res -= charVal ( S [ i ] ) ; else res += charVal ( S [ i ] ) ; } return res ; } string DecToRoman ( int number ) { string res = " " ; int num [ ] = { 1 , 4 , 5 , 9 , 10 , 40 , 50 , 90 , 100 , 400 , 500 , 900 , 1000 } ; string sym [ ] = { " I " , " IV " , " V " , " IX " , " X " , " XL " , " L " , " XC " , " C " , " CD " , " D " , " CM " , " M " } ; int i = 12 ; while ( number > 0 ) { int div = number / num [ i ] ; number = number % num [ i ] ; while ( div -- ) { res += sym [ i ] ; } i -- ; } return res ; } bool compare ( char x , char y ) { int val_x = charVal ( x ) ; int val_y = charVal ( y ) ; return ( val_x > val_y ) ; } string findLargest ( string S ) { set < char > st = { ' I ' , ' V ' , ' X ' , ' L ' , ' C ' , ' D ' , ' M ' } ; for ( auto x : S ) { if ( st . find ( x ) == st . end ( ) ) return " Invalid " ; } sort ( S . begin ( ) , S . end ( ) , compare ) ; int N = romanToDec ( S ) ; string R = DecToRoman ( N ) ; if ( S != R ) return " Invalid " ; return S ; } int main ( ) { string S = " MCMIV " ; cout << findLargest ( S ) ; }