Why doesn't my solution to LC 12 Integer to Roman work?

Question

What I don't understand is when I pass tmp-=1 to the function instead as it is returning 'X' for numbers less than 10 and 'C' for numbers less than 100 and greater than 10 it loops infinitely.

class Solution {

    int findNextDigit(int num)
    {
        
            int tmp = 0;
            int k = 1;

            while(Math.pow(10,tmp) *k < num)
            {
                if(num - Math.pow(10,tmp) < Math.pow(10,tmp) )
                {
                    k++;
                }

                else
                {
                    tmp++;
                }

            }
            
            return ((int)(Math.pow(10,tmp))*k);
    }
    public String intToRoman(int num) 
    {
        String ans = "";
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "I");
        map.put(5, "V");
        map.put(10,"X");
        map.put(50, "L");
        map.put(100, "C");
        map.put(500, "D");
        map.put(1000, "M");
        map.put(4, "IV");
        map.put(9, "IX");
        map.put(40, "XL");
        map.put(90, "XC");
        map.put(400, "CD");
        map.put(900, "CM");

        while(num>0)
        {
            int tmp = findNextDigit(num);
            ans+= map.get(tmp);
            num-=tmp;
        }   


        return ans;
        

    }
}

Answer 1

Your code has a couple of issues. The loop control variables tmp and k are not clearly designed. tmp is incrementing when num - Math.pow(10,tmp) is greater than or equal to Math.pow(10, tmp), and k is incrementing otherwise. This creates an ambiguity in the control of the loop, and in certain cases, it might not terminate.

You are initializing k to 1 and increasing it in the loop, but k is not really required in this context. The Roman numeral values are fixed and can be stored in an array or list.

public class Solution {
    
    int findNextDigit(int num, int[] values) {
        for (int value : values) {
            if (num >= value) {
                return value;
            }
        }
        return 0;
    }

    public String intToRoman(int num) {
        StringBuilder ans = new StringBuilder();

        // Define the Roman numeral values and their corresponding strings
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                ans.append(symbols[i]);
                num -= values[i];
            }
        }

        return ans.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.intToRoman(1994));  // Should print "MCMXCIV"
    }
}

In this specific case, using StringBuilder over String offers significant performance advantages because it avoids the overhead of creating multiple immutable String objects during concatenation.