Integer to English Words

hard math string recursion

Problem

Convert a non-negative integer num to its English words representation.

Inputnum = 1234567

Output"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Split into groups of three: 1 (Million) | 234 (Thousand) | 567.

num

ONES = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine",
        "Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen",
        "Seventeen","Eighteen","Nineteen"]
TENS = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
SCALE = ["","Thousand","Million","Billion"]

def under_1000(n):
    if n == 0: return ""
    if n < 20: return ONES[n]
    if n < 100: return TENS[n//10] + (" " + ONES[n%10] if n%10 else "")
    return ONES[n//100] + " Hundred" + (" " + under_1000(n%100) if n%100 else "")

def number_to_words(n):
    if n == 0: return "Zero"
    parts, i = [], 0
    while n > 0:
        chunk = n % 1000
        if chunk: parts.append(under_1000(chunk) + (" " + SCALE[i] if SCALE[i] else ""))
        n //= 1000; i += 1
    return " ".join(reversed(parts)).strip()

const ONES = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"];
const TENS = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"];
const SCALE = ["","Thousand","Million","Billion"];
function under1000(n) {
  if (n === 0) return "";
  if (n < 20) return ONES[n];
  if (n < 100) return TENS[Math.floor(n/10)] + (n%10 ? " " + ONES[n%10] : "");
  return ONES[Math.floor(n/100)] + " Hundred" + (n%100 ? " " + under1000(n%100) : "");
}
function numberToWords(n) {
  if (n === 0) return "Zero";
  const parts = []; let i = 0;
  while (n > 0) {
    const chunk = n % 1000;
    if (chunk) parts.push(under1000(chunk) + (SCALE[i] ? " " + SCALE[i] : ""));
    n = Math.floor(n / 1000); i++;
  }
  return parts.reverse().join(" ").trim();
}

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

vector<string> ONES = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
vector<string> TENS = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
vector<string> SCALE = {"","Thousand","Million","Billion"};
string under1000(int n) {
    if (n == 0) return "";
    if (n < 20) return ONES[n];
    if (n < 100) return TENS[n/10] + (n%10 ? " " + ONES[n%10] : "");
    return ONES[n/100] + " Hundred" + (n%100 ? " " + under1000(n%100) : "");
}
string numberToWords(int n) {
    if (n == 0) return "Zero";
    string out;
    int i = 0;
    while (n > 0) {
        int chunk = n % 1000;
        if (chunk) out = under1000(chunk) + (SCALE[i].empty() ? "" : " " + SCALE[i]) + " " + out;
        n /= 1000; i++;
    }
    while (!out.empty() && out.back() == ' ') out.pop_back();
    return out;
}

Explanation

The English language already groups big numbers into chunks of three digits — thousands, millions, billions — so the solution copies that idea: break the number into three-digit groups and name each one separately.

The helper under_1000 turns any number below 1000 into words. It handles three cases: numbers under 20 have unique names (looked up in ONES), numbers under 100 combine a tens word with a ones word, and hundreds say the leading digit plus "Hundred" then recurse on the remainder.

The main function peels off groups from the right using n % 1000 and n //= 1000. Each non-zero group gets its words plus the right scale word from SCALE (Thousand, Million, Billion) based on how many groups in we are. We collect these and join them in the correct left-to-right order.

Example: 1234567 splits into 1, 234, 567. These become "One Million", "Two Hundred Thirty Four Thousand", and "Five Hundred Sixty Seven", joined into the full phrase.

A small special case: if the whole number is 0, we just return "Zero" directly, since the loop would otherwise produce nothing.

Time: O(log n) Space: O(log n)