Integer to English Words
Integer to English Words is a hard arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (iterative groups of three), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive descent by magnitude up.
Problem
Convert a non-negative integer num into its English words, with each word capitalised and words separated by single spaces.
Use the short-scale names Thousand, Million and Billion, the word Hundred inside each three-digit group, and no “and” or hyphens (for example Forty Two, not forty-two). Groups that are entirely zero are not spoken.
Examples
Example 1
- Input
num = 507- Output
"Five Hundred Seven"- Why
- The zero tens digit is simply not spoken.
Example 2
- Input
num = 1000010- Output
"One Million Ten"- Why
- The thousands group is 000, so the word "Thousand" is skipped entirely.
Example 3
- Input
num = 0- Output
"Zero"- Why
- Zero is the only number that is spelled with the word "Zero".
Constraints
0 <= num <= 2^31 - 1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive descent by magnitude | O(1) | O(1) |
| Optimal (iterative groups of three) | O(1) | O(1) |
1Recursive descent by magnitude
O(1)The input has at most 10 digits, so there are a bounded number of recursive calls.O(1)Recursion depth and output length are bounded by constants.Write a function words(n) that peels off the largest unit it can: billions, millions, thousands, hundreds, tens, and finally the words below 20. Each case recurses on the quotient and the remainder and joins the non-empty parts with single spaces.
- If num == 0 return "Zero".
- words(n): n == 0 → ""; n < 20 → BELOW_20[n]; n < 100 → TENS[n / 10] + words(n % 10).
- n < 1000 → words(n / 100) + "Hundred" + words(n % 100); then the same for 10^6 (Thousand), 10^9 (Million) and the rest (Billion).
- Join with a helper that adds a space only between two non-empty parts.
class Solution {
private static final String[] BELOW_20 = { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
"Seventeen", "Eighteen", "Nineteen" };
private static final String[] TENS = { "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy",
"Eighty", "Ninety" };
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
return words(num);
}
private String words(int n) {
if (n == 0) return "";
if (n < 20) return BELOW_20[n];
if (n < 100) return join(TENS[n / 10], words(n % 10));
if (n < 1000) return join(words(n / 100) + " Hundred", words(n % 100));
if (n < 1_000_000) return join(words(n / 1000) + " Thousand", words(n % 1000));
if (n < 1_000_000_000) return join(words(n / 1_000_000) + " Million", words(n % 1_000_000));
return join(words(n / 1_000_000_000) + " Billion", words(n % 1_000_000_000));
}
private String join(String a, String b) {
if (b.isEmpty()) return a;
return a + " " + b;
}
}class Solution:
BELOW_20 = ["", "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"]
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
return self.words(num)
def words(self, n: int) -> str:
if n == 0:
return ""
if n < 20:
return self.BELOW_20[n]
if n < 100:
return self.join(self.TENS[n // 10], self.words(n % 10))
if n < 1000:
return self.join(self.words(n // 100) + " Hundred", self.words(n % 100))
if n < 1_000_000:
return self.join(self.words(n // 1000) + " Thousand", self.words(n % 1000))
if n < 1_000_000_000:
return self.join(self.words(n // 1_000_000) + " Million", self.words(n % 1_000_000))
return self.join(self.words(n // 1_000_000_000) + " Billion", self.words(n % 1_000_000_000))
def join(self, a: str, b: str) -> str:
return a if not b else a + " " + bclass Solution {
vector<string> BELOW_20 = { "", "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" };
public:
string numberToWords(int num) {
if (num == 0) return "Zero";
return words(num);
}
private:
string words(int n) {
if (n == 0) return "";
if (n < 20) return BELOW_20[n];
if (n < 100) return join(TENS[n / 10], words(n % 10));
if (n < 1000) return join(words(n / 100) + " Hundred", words(n % 100));
if (n < 1000000) return join(words(n / 1000) + " Thousand", words(n % 1000));
if (n < 1000000000) return join(words(n / 1000000) + " Million", words(n % 1000000));
return join(words(n / 1000000000) + " Billion", words(n % 1000000000));
}
string join(const string& a, const string& b) {
if (b.empty()) return a;
return a + " " + b;
}
};const BELOW_20 = ["", "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"];
function numberToWords(num) {
if (num === 0) return "Zero";
return words(num);
}
function words(n) {
if (n === 0) return "";
if (n < 20) return BELOW_20[n];
if (n < 100) return join(TENS[Math.floor(n / 10)], words(n % 10));
if (n < 1000) return join(words(Math.floor(n / 100)) + " Hundred", words(n % 100));
if (n < 1e6) return join(words(Math.floor(n / 1000)) + " Thousand", words(n % 1000));
if (n < 1e9) return join(words(Math.floor(n / 1e6)) + " Million", words(n % 1e6));
return join(words(Math.floor(n / 1e9)) + " Billion", words(n % 1e9));
}
function join(a, b) {
return b === "" ? a : a + " " + b;
}2Optimal (iterative groups of three)
O(1)At most four groups, each spelled in constant time.O(1)A bounded number of words is stored.Split the number into 3-digit groups from the right. Spell each non-zero group with one small helper (hundreds, then below-20 or tens + ones), append the scale word for its position ("", Thousand, Million, Billion), and put it in front of what has been built so far. Words are collected in a list and joined once, so spacing is always clean.
- If num == 0 return "Zero".
- scale = 0; while num > 0: group = num % 1000. If group > 0, build its words, add SCALES[scale] if non-empty, and prepend them to the result.
- num /= 1000, scale++.
- Join all words with single spaces.
class Solution {
private static final String[] BELOW_20 = { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
"Seventeen", "Eighteen", "Nineteen" };
private static final String[] TENS = { "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy",
"Eighty", "Ninety" };
private static final String[] SCALES = { "", "Thousand", "Million", "Billion" };
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
List<String> result = new ArrayList<>();
int scale = 0;
while (num > 0) {
int group = num % 1000;
if (group > 0) {
List<String> part = new ArrayList<>();
if (group >= 100) {
part.add(BELOW_20[group / 100]);
part.add("Hundred");
}
int rest = group % 100;
if (rest >= 20) {
part.add(TENS[rest / 10]);
if (rest % 10 > 0) part.add(BELOW_20[rest % 10]);
} else if (rest > 0) {
part.add(BELOW_20[rest]);
}
if (!SCALES[scale].isEmpty()) part.add(SCALES[scale]);
result.addAll(0, part);
}
num /= 1000;
scale++;
}
return String.join(" ", result);
}
}class Solution:
BELOW_20 = ["", "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"]
SCALES = ["", "Thousand", "Million", "Billion"]
def numberToWords(self, num: int) -> str:
if num == 0:
return "Zero"
result = []
scale = 0
while num > 0:
group = num % 1000
if group > 0:
part = []
if group >= 100:
part += [self.BELOW_20[group // 100], "Hundred"]
rest = group % 100
if rest >= 20:
part.append(self.TENS[rest // 10])
if rest % 10 > 0:
part.append(self.BELOW_20[rest % 10])
elif rest > 0:
part.append(self.BELOW_20[rest])
if self.SCALES[scale]:
part.append(self.SCALES[scale])
result = part + result
num //= 1000
scale += 1
return " ".join(result)class Solution {
vector<string> BELOW_20 = { "", "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> SCALES = { "", "Thousand", "Million", "Billion" };
public:
string numberToWords(int num) {
if (num == 0) return "Zero";
vector<string> result;
int scale = 0;
while (num > 0) {
int group = num % 1000;
if (group > 0) {
vector<string> part;
if (group >= 100) {
part.push_back(BELOW_20[group / 100]);
part.push_back("Hundred");
}
int rest = group % 100;
if (rest >= 20) {
part.push_back(TENS[rest / 10]);
if (rest % 10 > 0) part.push_back(BELOW_20[rest % 10]);
} else if (rest > 0) {
part.push_back(BELOW_20[rest]);
}
if (!SCALES[scale].empty()) part.push_back(SCALES[scale]);
result.insert(result.begin(), part.begin(), part.end());
}
num /= 1000;
scale++;
}
string out;
for (size_t i = 0; i < result.size(); i++) {
if (i > 0) out += " ";
out += result[i];
}
return out;
}
};function numberToWords(num) {
const BELOW_20 = ["", "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 SCALES = ["", "Thousand", "Million", "Billion"];
if (num === 0) return "Zero";
let result = [];
let scale = 0;
while (num > 0) {
const group = num % 1000;
if (group > 0) {
const part = [];
if (group >= 100) part.push(BELOW_20[Math.floor(group / 100)], "Hundred");
const rest = group % 100;
if (rest >= 20) {
part.push(TENS[Math.floor(rest / 10)]);
if (rest % 10 > 0) part.push(BELOW_20[rest % 10]);
} else if (rest > 0) {
part.push(BELOW_20[rest]);
}
if (SCALES[scale]) part.push(SCALES[scale]);
result = part.concat(result);
}
num = Math.floor(num / 1000);
scale++;
}
return result.join(" ");
}Edge cases to test
num = 0- Teens 10-19, which have their own words
- A whole group of zeros in the middle (1,000,005)
- Exact round numbers (1,000,000,000) with no trailing words
- The largest value 2,147,483,647
Hints
Hint 1
English names numbers in groups of three digits: units, Thousand, Million, Billion. Every group is spelled the same way.
Hint 2
Spell a number below 1000 as: hundreds digit + "Hundred", then either a word below 20 or a tens word followed by a ones word.
Hint 3
Skip any group equal to 0, and be careful not to leave double or trailing spaces.
FAQ
What is the best time complexity for Integer to English Words?
Optimal (iterative groups of three) runs in O(1) time and O(1) extra space. At most four groups, each spelled in constant time.
Which pattern does Integer to English Words use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, String to Integer (atoi), Remove Comments.
Is there a brute force solution for Integer to English Words?
Yes. Recursive descent by magnitude takes O(1) time and O(1) space. Write a function words(n) that peels off the largest unit it can: billions, millions, thousands, hundreds, tens, and finally the words below 20.
Which edge cases should I test for Integer to English Words?
num = 0; Teens 10-19, which have their own words; A whole group of zeros in the middle (1,000,005); Exact round numbers (1,000,000,000) with no trailing words; The largest value 2,147,483,647.