Given a string S of length N, the task is to print the highest roman number possible by rearranging the characters of the given string, if the given string is a valid roman number. If found to be not possible, then print “Invalid”.
Examples:
Input: S = “MCMIV”
Output: MMCVI
Explanation: The given string S is valid Roman numeral. Rearranging characters to obtain the string “MMCVI” generates the highest roman numeral possible using given set of characters.Input: S = “XCYVM”
Output: Invalid
Approach: The idea is to use the sorting by the second element. Follow the steps below to solve the problem:
- Iterate over the characters of the string.
- Check if the string contains any character other than { ‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’ } or not. If found to be true, then print “Invalid”.
- Otherwise, sort the string in descending order with respect to the decimal value of the characters of the string.
- Now convert the roman value to equivalent decimal and store it in a variable, say X.
- Now find the equivalent roman value of the decimal number X and store it in a variable, say Y.
- Now print the string S if S is found to be equal to Y. Otherwise print “Invalid”.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find decimal// value of a roman characterint 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;}// Function to convert string representing// roman number to equivalent decimal valueint romanToDec(string S){ // Stores the decimal value // of the string S int res = 0; // Stores the size of the S int n = S.size(); // Update res res = charVal(S[n - 1]); // Traverse the string 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 return res;}// Function to convert decimal// to equivalent roman numeralstring DecToRoman(int number){ // Stores the string string res = ""; // Stores all the digit values of a roman digit 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; // Iterate while number // is greater than 0 while (number > 0) { int div = number / num[i]; number = number % num[i]; while (div--) { res += sym[i]; } i--; } // Return res return res;}// Function to sort the string// in descending order of values// assigned to charactersbool compare(char x, char y){ // Return character with // highest decimal value int val_x = charVal(x); int val_y = charVal(y); return (val_x > val_y);}// Function to find largest roman// value possible by rearranging// the characters of the stringstring findLargest(string S){ // Stores all roman characters set<char> st = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' }; // Traverse the string for (auto x : S) { // If X is not found if (st.find(x) == st.end()) return "Invalid"; } sort(S.begin(), S.end(), compare); // Stores the decimal value // of the roman number int N = romanToDec(S); // Find the roman value equivalent // to the decimal value of N string R = DecToRoman(N); if (S != R) return "Invalid"; // Return result return S;}// Driver Codeint main(){ string S = "MCMIV"; cout << findLargest(S);} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find decimal// value of a roman characterstatic 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;}// Function to convert string representing// roman number to equivalent decimal valuestatic int romanToDec(String S){ // Stores the decimal value // of the string S int res = 0; // Stores the size of the S int n = S.length(); // Update res res = charVal(S.charAt(n - 1)); // Traverse the string for(int i = n - 2; i >= 0; i--) { if (charVal(S.charAt(i)) < charVal(S.charAt(i + 1))) res -= charVal(S.charAt(i)); else res += charVal(S.charAt(i)); } // Return res return res;}// Function to convert decimal// to equivalent roman numeralstatic String DecToRoman(int number){ // Stores the string String res = ""; // Stores all the digit values of a roman digit 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; // Iterate while number // is greater than 0 while (number > 0) { int div = number / num[i]; number = number % num[i]; while (div-- > 0) { res += sym[i]; } i--; } // Return res return res;}// Function to find largest roman// value possible by rearranging// the characters of the stringstatic String findLargest(String S){ char arr[] = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' }; // Stores all roman characters Set<Character> st = new HashSet<>(); for(char x : arr) st.add(x); Character s[] = new Character[S.length()]; for(int i = 0; i < S.length(); i++) s[i] = S.charAt(i); // Traverse the string for(char x : s) { // If X is not found if (!st.contains(x)) return "Invalid"; } Arrays.sort(s, new Comparator<Character>() { @Override public int compare(Character x, Character y) { return charVal(y) - charVal(x); } }); String ss = ""; for(char ch : s) ss += ch; // Stores the decimal value // of the roman number int N = romanToDec(ss); // Find the roman value equivalent // to the decimal value of N String R = DecToRoman(N); if (!ss.equals(R)) return "Invalid"; // Return result return ss;}// Driver Codepublic static void main(String[] args){ // Input String S = "MCMIV"; int N = S.length(); System.out.println(findLargest(S));}}// This code is contributed by Kingash |
Python3
# Python program for the above approach# Function to find decimal# value of a roman characterfrom functools import cmp_to_keydef mycmp(a, b): return -charVal(a) + charVal(b)def charVal(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# Function to convert string representing# roman number to equivalent decimal valuedef romanToDec(S): # Stores the decimal value # of the string S res = 0 # Stores the size of the S n = len(S) # Update res res = charVal(S[n - 1]) # Traverse the string for i in range(n-2,-1,-1): if (charVal(S[i]) < charVal(S[i + 1])): res -= charVal(S[i]) else: res += charVal(S[i]) # Return res return res# Function to convert decimal# to equivalent roman numeraldef DecToRoman(number): # Stores the string res = "" # Stores all the digit values of a roman digit num = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000] sym = ["I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"] i = 12 # Iterate while number # is greater than 0 while (number > 0): div = number // num[i] number = number % num[i] while (div > 0): res += sym[i] div -= 1 i -= 1 # Return res return res# Function to find largest roman# value possible by rearranging# the characters of the stringdef findLargest(S): arr = ['I', 'V', 'X', 'L', 'C', 'D', 'M'] # Stores all roman characters st = set() for x in arr: st.add(x) s = [0 for i in range(len(S))] for i in range(len(S)): s[i] = S[i] # Traverse the string for x in s: # If X is not found if (x not in st): return "Invalid" s.sort(key = cmp_to_key(mycmp)) ss = "" for ch in s: ss += ch # Stores the decimal value # of the roman number N = romanToDec(ss) # Find the roman value equivalent # to the decimal value of N R = DecToRoman(N) if (ss != R): return "Invalid" # Return result return ss# Driver Code# InputS = "MCMIV"N = len(S)print(findLargest(S))# This code is contributed by Shinjanapatra |
C#
using System;using System.Collections.Generic;class Program { // Function to find decimal // value of a roman character static 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; } // Function to convert string representing // roman number to equivalent decimal value static int RomanToDec(string S) { // Stores the decimal value // of the string S int res = 0; // Stores the size of the S int n = S.Length; /// Update res res = CharVal(S[n - 1]); // Traverse the string 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; } // Function to convert decimal // to equivalent roman numeral static string DecToRoman(int number) { // Stores the string string res = ""; // Stores all the digit values of a roman digit 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" }; // Iterate while number // is greater than 0 int i = 12; while (number > 0) { int div = number / num[i]; number = number % num[i]; while (div-- > 0) { res += sym[i]; } i--; } return res; } // Function to find largest roman // value possible by rearranging // the characters of the string static string FindLargest(string S) { // Stores all roman characters char[] arr = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' }; // Traverse the string HashSet<char> st = new HashSet<char>(); foreach(char x in arr) st.Add(x); char[] s = new char[S.Length]; for (int i = 0; i < S.Length; i++) s[i] = S[i]; foreach(char x in s) { if (!st.Contains(x)) return "Invalid"; } Array.Sort(s, delegate(char x, char y) { return CharVal(y) - CharVal(x); }); string ss = ""; foreach(char ch in s) ss += ch; // Stores the decimal value // of the roman number int N = RomanToDec(ss); // Find the roman value equivalent // to the decimal value of N string R = DecToRoman(N); if (!ss.Equals(R)) return "Invalid"; return ss; } // Driver code static void Main(string[] args) { string S = "MCMIV"; Console.WriteLine(FindLargest(S)); }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript program for the above approach// Function to find decimal// value of a roman characterfunction charVal(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;}// Function to convert string representing// roman number to equivalent decimal valuefunction romanToDec(S) { // Stores the decimal value // of the string S let res = 0; // Stores the size of the S let n = S.length; // Update res res = charVal(S[n - 1]); // Traverse the string for (let 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 return res;}// Function to convert decimal// to equivalent roman numeralfunction DecToRoman(number) { // Stores the string let res = ""; // Stores all the digit values of a roman digit let num = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000]; let sym = ["I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"]; let i = 12; // Iterate while number // is greater than 0 while (number > 0) { let div = Math.floor(number / num[i]); number = number % num[i]; while (div-- > 0) { res += sym[i]; } i--; } // Return res return res;}// Function to find largest roman// value possible by rearranging// the characters of the stringfunction findLargest(S) { let arr = ['I', 'V', 'X', 'L', 'C', 'D', 'M']; // Stores all roman characters let st = new Set(); for (let x of arr) st.add(x); let s = new Array(S.length); for (let i = 0; i < S.length; i++) s[i] = S[i]; // Traverse the string for (let x of s) { // If X is not found if (!st.has(x)) return "Invalid"; } s.sort((a, b) => -charVal(a) + charVal(b)) let ss = ""; for (let ch of s) ss += ch; // Stores the decimal value // of the roman number let N = romanToDec(ss); // Find the roman value equivalent // to the decimal value of N let R = DecToRoman(N); if (ss != R) return "Invalid"; // Return result return ss;}// Driver Code// Inputlet S = "MCMIV";let N = S.length;document.write(findLargest(S));// This code is contributed by Saurabh Jaiswal</script> |
Output:
MMCVI
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
