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.