Solution by rohitnandi12


  • 0
    R

    Step1 If you are not Roman and have little or no knowledge on Roman Number System, you should definitely go through this article of Roman Numerals to solve this problem

    Step2 Try to solve some examples manually. For example try to convert "MMXVI" to its integer equivalent.
    Unlike Decimal system where a digit in a number has a face and place value (eg. In 567, 6 has face value = 6 and place value = 60 ) in Roman number system a symbol denotes the value it is contributing to the number (eg in "MMXVI", M means 1000 and MM means 1000 + 1000 )

    Therefore, "MMXVI" = 1000 + 1000 + 10 + 5 + 1 = 2016

    Approach #1 Implementation [ Accepted ]

    Intuition
    The question is no more to detect what the number is but to add or subtract the symbol value based on two condition

    • if a symbol is followed by a symbol having smaller or equal value then that symbol is added. (eg "MMX) = 1000 + 1000 + 10 = 2010
    • if a symbol is followed by a symbol having greater value then that small value is subtracted and not added. (eg "MMXIV) = 1000 + 1000 + 10 - 1 + 5 = 2014 . Here "I" is subtracted, because it is followed by "V". "IV" is four because (-1 + 5 = 4 ).

    Algorithm

    • Iterate over the characters in s
      • if character is not followed by any character with greater value, add character value to result.
      • if character is followed by any character with greater value, subtract character value from result

    Java

    class Solution {
        public int romanToInt(String s) {
            
            if(s == null)return 0;
            s = s.toUpperCase();
            
            HashMap<Character,Integer> lu = new HashMap<>(); // lookUp
            lu.put('I',1);
            lu.put('V',5);
            lu.put('X',10);
            lu.put('L',50);
            lu.put('C',100);
            lu.put('D',500);
            lu.put('M',1000);
            
            int i=0,currentVal = 0, num=0;
            for(i=0; i<s.length()-1; i++){
                currentVal = lu.get(s.charAt(i));
                
                if(currentVal < lu.get(s.charAt(i+1))){
                    num -= currentVal;
                }else{
                    num += currentVal;
                }
                
            }
            num += lu.get(s.charAt(i));
            
            return num;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

  • 0
    E

    @rohitnandi12 This solution would never inspect the last number


  • 0
    R

    @edd91 The last number is handled by the line "num += lu.get(s.charAt(i));" before the return statement


  • 0
    E

    @rohitnandi12 I see. Would you not then incorrectly count a last character that is also bigger than the one before it? i.e. for 'XIV' it would add the V without regard to the fact it is part of the IV.


  • 0
    R

    @edd91 I have changed the post a bit, to make it more clear. I hope your doubt is now solved. Dont think it as a problem of detection of numbers, but to evaluate the final result.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.