273. Integer to English Words
- Math
- String
- Recursion
TIME
O(1), at most 4 chunks of 3 digits
SPACE
O(1)
Intuition
English reads numbers in groups of three digits. 1,234,567 is "one million", "two hundred thirty four thousand", "five hundred sixty seven". Each group is said the same way, as a number from 1 to 999, followed by its scale word. So the whole problem is a 1 to 999 converter plus a loop over at most four groups (2^31 - 1 is just over two billion).
Inside a group, 1 to 19 are irregular names, 20 to 99 are a tens word plus an optional ones word, and a nonzero hundreds digit adds "X Hundred" in front.
The hard part is the spacing and the zeros, not the math.
Approach
0is the only number whose answer contains "Zero"; return it directly.- For scale
3, 2, 1, 0(Billion, Million, Thousand, none), take the chunknum / 1000^scale % 1000. - Skip a zero chunk entirely, so that 1,000,000 doesn't produce "One Million Thousand".
- For a nonzero chunk, emit
ones[h] Hundredif the hundreds digithis nonzero. For the last two digitsr, emitones[r]ifr < 20, elsetens[r / 10]plusones[r % 10]. Then emit the scale word. - Collect words in a list, drop the empty ones (
ones[0],scales[0], the ones word of 20, 30, ...), and join with single spaces.
Complexity
- Time: O(1). At most 4 chunks and a bounded number of words.
- Space: O(1)
Edge Cases
0→"Zero", the only case that uses the word- Zero chunks in the middle: 1,000,010 is "One Million Ten" (no "Thousand"), and 1,001,000 is "One Million One Thousand"
- Exact tens and hundreds (20, 100, 1000): no trailing "Zero" and no trailing space
- 10 to 19 inside a chunk (110 is "One Hundred Ten", not "One Hundred One Zero")
- No "and" anywhere: LeetCode expects "One Hundred One", not "One Hundred and One"
2^31 - 1reaches the Billion chunk; the Java loop starts its divisor at10^9, which still fits inint
Code
class Solution:
def numberToWords(self, num: int) -> str:
"""
273. Integer to English Words
Time: O(1), at most 4 chunks of 3 digits
Space: O(1)
"""
if num == 0:
return "Zero"
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"]
scales = ["", "Thousand", "Million", "Billion"]
def chunk(n: int) -> list[str]:
# Words for 1 <= n <= 999. Empty strings are filtered out later.
hundreds, rest = divmod(n, 100)
words = [ones[hundreds], "Hundred"] if hundreds else []
if rest < 20:
words.append(ones[rest])
else:
words += [tens[rest // 10], ones[rest % 10]]
return words
words = []
for scale in range(3, -1, -1):
n = num // 1000**scale % 1000
if n: # a zero chunk adds nothing, not even its scale word
words += chunk(n) + [scales[scale]]
return " ".join(w for w in words if w)/**
* 273. Integer to English Words
* Time: O(1), at most 4 chunks of 3 digits
* Space: O(1)
*/
class Solution {
private static final String[] ONES = {"", "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";
}
StringBuilder sb = new StringBuilder();
int divisor = 1_000_000_000;
for (int scale = 3; scale >= 0; scale--, divisor /= 1000) {
int n = num / divisor % 1000;
if (n != 0) { // a zero chunk adds nothing, not even its scale word
appendChunk(sb, n);
add(sb, SCALES[scale]);
}
}
return sb.toString();
}
// Words for 1 <= n <= 999.
private void appendChunk(StringBuilder sb, int n) {
int hundreds = n / 100, rest = n % 100;
if (hundreds != 0) {
add(sb, ONES[hundreds]);
add(sb, "Hundred");
}
if (rest < 20) {
add(sb, ONES[rest]);
} else {
add(sb, TENS[rest / 10]);
add(sb, ONES[rest % 10]);
}
}
// Appends a word with a single separating space; empty words are skipped.
private void add(StringBuilder sb, String word) {
if (word.isEmpty()) {
return;
}
if (sb.length() > 0) {
sb.append(' ');
}
sb.append(word);
}
}