Reference: LeetCode
Difficulty: Hard

Problem

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than $2^{31} - 1$.

Note:

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input: 0
Output: "Zero"

Input: 20
Output: "Twenty"

Input: 100
Output: "One Hundred"

Input: 123
Output: "One Hundred Twenty Three"

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

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

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Analysis

Divide and Conquer

Consider write a function that calculates the number below 1000, which is used many places, e.g. 345 Billion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
public String numberToWords(int num) {
// Assume num > 0
if (num == 0) { // Zero
return digit2Str(0);
}
StringBuilder sb = new StringBuilder();
while (num != 0) {
// billion
if (num >= (int) 1e9) {
int d = num / (int) 1e9;
sb.append(stringBelowThousand(d) + " Billion" + " ");
num %= (int) 1e9;
}
// million
else if (num >= (int) 1e6) {
int d = num / (int) 1e6;
System.out.println(d);
sb.append(stringBelowThousand(d) + " Million" + " ");
num %= (int) 1e6;
}
// thousand
else if (num >= (int) 1e3) {
int d = num / (int) 1e3;
sb.append(stringBelowThousand(d) + " Thousand" + " ");
num %= (int) 1e3;
}
// < 1000
else {
sb.append(stringBelowThousand(num));
num = 0;
}
}
return sb.toString().trim(); // for last " "
}


private String stringBelowThousand(int d) {
if (d < 100) {
return tenth2Str(d / 10, d % 10);
}
// hundreds
else if (d >= 100 && d < 1000) {
int tenth = (d % 100) / 10;
int digit = (d % 100) % 10;
if (tenth == 0 && digit == 0) {
return digit2Str(d / 100) + " Hundred"; // 100, 200, 300, ...
} else {
return digit2Str(d / 100) + " Hundred " + tenth2Str(tenth, digit);
}
} else {
throw new IllegalArgumentException("invalid input in stringBelowThousand");
}
}


private String digit2Str(int digit) {
if (digit == 0) return "Zero";
if (digit == 1) return "One";
if (digit == 2) return "Two";
if (digit == 3) return "Three";
if (digit == 4) return "Four";
if (digit == 5) return "Five";
if (digit == 6) return "Six";
if (digit == 7) return "Seven";
if (digit == 8) return "Eight";
if (digit == 9) return "Nine";
throw new IllegalArgumentException("invalid input in digit2Str");
}


private String tenth2Str(int tenth, int digit) {
if (tenth < 0 || tenth > 9 || digit < 0 || digit > 9) {
throw new IllegalArgumentException("invalid input in tenth2Str");
}
if (tenth == 0) return digit2Str(digit);
if (tenth == 1) return tenth2StrHelper(digit);
String ret = "";
if (tenth == 2) ret = "Twenty";
if (tenth == 3) ret = "Thirty";
if (tenth == 4) ret = "Forty";
if (tenth == 5) ret = "Fifty";
if (tenth == 6) ret = "Sixty";
if (tenth == 7) ret = "Seventy";
if (tenth == 8) ret = "Eighty";
if (tenth == 9) ret = "Ninety";
if (digit != 0) { // e.g. 20
return ret + " " + digit2Str(digit);
} else {
return ret;
}
}


private String tenth2StrHelper(int digit) { // 11, 12, 13, 14, 15, 16, ...
if (digit == 0) return "Ten";
if (digit == 1) return "Eleven";
if (digit == 2) return "Twelve";
if (digit == 3) return "Thirteen";
if (digit == 4) return "Fourteen";
if (digit == 5) return "Fifteen";
if (digit == 6) return "Sixteen";
if (digit == 7) return "Seventeen";
if (digit == 8) return "Eighteen";
if (digit == 9) return "Nineteen";
throw new IllegalArgumentException("invalid input in tenth2StrHelper");
}

Time: $O(N)$ where $N$ is the number of digits.
Space: $O(1)$ or $O(N)$ if we count the output String Builder.


Comment