The O(n) Club: Integer to English Words — There’s Nothing Regular About English, Sorry

The O(n) Club: Integer to English Words — There’s Nothing Regular About English, Sorry

⚡ TL;DR

You’re converting a number like 12345 into “Twelve Thousand Three Hundred Forty Five” (and no, Google Translate won’t bail you out). Brute force means writing out every possible variant, which is the dev equivalent of tiling your bathroom floor with a toothbrush.

// Brute-force brain-melter
if (num == 0) return "Zero";
// Else, chunk number per 3 digits
// Map chunk: "", "Thousand", "Million", "Billion"

🧠 How Devs Usually Mess This Up

Step one: Assume English is logical. Rookie mistake. You’ll try to apply tidy digit patterns, then instantly trip on ‘Twelve’, ‘Eleven’, and teens that refuse to follow adult rules. Next? Reverse-word salad: write code that says “Thousand Thirty Five Million”. Hint: People hate that. Also, Java’s string handling will slip trailing spaces in like uninvited guests at your party.

🔍 What’s Actually Going On

Break the number into 3-digit “chunks” like a deli counter serving up just hundreds, tens, and ones at a time. Each chunk gets paired with a scale – Thousand, Million, or Billion (because apparently, English ran out of new ideas after that). The secret sauce? A helper function recursively translates numbers < 1000 with lookup arrays for "belowTwenty" and "tens". Once you trust the helper, pipe together the chunks from most to least significant — aka left to right, like someone who went to school.

🛠️ PseudoCode

• Check Zero First: If num == 0, just return “Zero”. Only English makes you spell out zero special.
• Prepare Lookup Arrays:
  

  String[] belowTwenty = {...};
  String[] tens = {...};
  String[] thousands = {"", "Thousand", "Million", "Billion"};

  Those are your Rosetta Stone for weird number names.
• Chunk Away (Right to Left):
  

  for each chunk of 3 digits:
      if chunk != 0:
          helper(chunk) + thousands[i]

  No “Zero Million”, ever.
• Helper for < 1000:
  

  if number == 0: return ""
  if number < 20: return belowTwenty[number] + " "
  if number < 100: return tens[number / 10] + " " + helper(number % 10)
  else: return belowTwenty[number / 100] + " Hundred " + helper(number % 100)

  Recursion: prepping for job interviews or existential crises.
• Paste parts, trim spaces, and enjoy your masterpiece.

💻 The Code

public class Solution {
    private final String[] belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] thousands = {"", "Thousand", "Million", "Billion"};
     public String numberToWords(int num) {
        if (num == 0) return "Zero";
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (num > 0) {
            int chunk = num % 1000;
            if (chunk != 0) {
                result.insert(0, helper(chunk) + thousands[i] + " ");
            }
            num /= 1000;
            i++;
        }
        return result.toString().trim();
    }
    private String helper(int num) {
        if (num == 0) return "";
        if (num < 20) return belowTwenty[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        return belowTwenty[num / 100] + " Hundred " + helper(num % 100);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Pitfall: Zero — Special-cased. Your code should say “Zero”, not “Thousand Zero” or similar grammar disasters.
• Whitespace Woes — Use .trim() because that recursive spacing is a mess otherwise.
• Scale Yourself — 32-bit integer land only gets you up to billions. Want trillions? Bring more lookup tables (or lots of copy-paste energy).
• Complexity: O(1) for time and space in real use; the number of chunks is capped. No surprises unless your input is “infinite”.

🧠 Interviewer Brain-Tattoo

“If English made sense, this would be two lines. Instead, you learn recursion, array lookups — and that spaces are the dark matter of Java strings.”