class Solution {
    public String intToRoman(int num) {
        int[] nums = new int[]{1000, 900, 800, 700, 600, 500, 400, 300, 200, 100, 
            90, 80, 70, 60, 50, 40, 30, 20, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        String[] romans = new String[]{"M", "CM", "DCCC", "DCC", "DC", "D", "CD", "CCC", "CC", "C",
            "XC", "LXXX", "LXX", "LX", "L", "XL", "XXX", "XX", "X", "IX", "VIII", "VII", "VI", "V",
            "IV", "III", "II", "I"};
        
        int index = 0;
        String result = "";
        while (num > 0) {
            if (num < nums[index]) index++;
            else{
                num -= nums[index];
                result = result + romans[index];
            }
        }
        return result;
    }
}