The O(n) Club: Integer to Roman – How to Greedily Conquer Antiquity with Java

The O(n) Club: Integer to Roman – How to Greedily Conquer Antiquity with Java

⚡ TL;DR

Need to translate boring numbers into Roman numerals for everything from clocks to sequels? Just go big to small, slap on those symbols, and avoid the rookie mistakes. Here’s the Java cheat code:

// Greedy: go from largest to smallest, stick symbols until there’s nothing left
int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] numerals = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder sb = new StringBuilder();
for(int i=0; num>0; i++) {
    while(num >= values[i]) {
        num -= values[i];
        sb.append(numerals[i]);
    }
}
return sb.toString();

🧠 How Devs Usually Mess This Up

Classic mistake: treating Roman numerals like Lego bricks. “Why not just keep adding ‘I’ for every 1?” Because Romans (shockingly) preferred readability over repetition. If your solution says ‘IIII’ instead of ‘IV’, it’s time to take a coffee break and re-read the rules. Subtractive notation exists so your numerals don’t look like someone fell asleep on the keyboard.

🔍 What’s Actually Going On

Think of the greedy algorithm as a child at an ice cream shop—they’ll scoop as many ‘M’s as possible before moving on to the ‘D’s, then ‘C’s, and so on. Every now and then (for numbers like 4, 9, 40, 90, 400, 900), Rome throws a dramatic twist: a smaller value stuck before a bigger one (‘IV’, ‘IX’, etc.). Handle the simple and the drama with a lookup table, in descending order, and the rest is ancient history.

🛠️ PseudoCode

• Set up value-symbol pairs:

  values = [1000, 900, 500, 400, ...]
  symbols = ["M", "CM", "D", "CD", ...]

  Add includes for the spicy subtractive cases like 900, 400, 90, etc. Forget these and your answer won’t pass the Colosseum inspection.

• Loop and match:

  for each i = 0 to values.length - 1:

  Greedily subtract values[i], append symbols[i] until you run out of integer.

• Subtract-and-append dance:

  while (num >= values[i]):
      num -= values[i]
      romanString += symbols[i]

  Milk each value for all its worth, even if your number is a hodgepodge.

• Exit when num == 0:

  Congrats, you’ve built a numeral fit for Caesar’s wristwatch.

💻 The Code

public String intToRoman(int num) {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < values.length && num > 0; i++) {
        while (num >= values[i]) {
            num -= values[i];
            sb.append(numerals[i]);
        }
    }
    return sb.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t ignore subtractive pairs: If you see ‘IIII’, it’s time to phone a friend (or the History Channel).
• Keep it top-heavy: Always process from largest to smallest; bottom-up is the fast lane to disaster.
• Input boundaries: The algorithm won’t scale to 9999. LeetCode and the Romans both tap out at 3999.
• Complexity lowdown: Only a fixed number of symbols and steps every time. Feels O(1), looks O(1), is O(1). Caesar would approve.

🧠 Interviewer Brain-Tattoo

“If your Roman numerals are longer than the credits of a Marvel movie, subtractive notation is missing—and so is your offer letter.”