[LeetCode] 273. Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Thought process:
Iterate the number from right to left. One thousand at a time. For each thousand, iterate through the digits from right to left. Based on the index of the current digit, there are several cases:

1. index == 1: 
1. digit == 0:
1. left > 0: append "x-ty" to words. Increment index and right shift number.
2. left == 0: continue.
2. left == 1:
1. append "x-teen" to words. Increment index and right shift number.
3. Otherwise, append number to words.
2. index == 2:
1. digit == 0: continue.
2. digit > 0: since the special cases are already covered in the previous case. Append "x-ty" to words.
3. index == 3:
1. digit == 0: continue;
2. digit > 0: append "number Hundred" to words.

At the end of each thousand, append "Thousand", "Million", or "Billion" based on loop index.

Solution:

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

class Solution { public String numberToWords(int num) { if (num == 0) { return "Zero"; } String[] ones = { "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" }; String[] teens = { "", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" }; String[] tens = { "", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" }; int thousand = 0; String words = ""; while (num > 0) { int index = 0; int mod = num % 1000; while (mod > 0) { int digit = mod % 10; int left = mod % 100 / 10; if (index == 0) { if (digit == 0) { if (left > 0) { words = " " + tens[left] + words; index++; mod /= 10; } } else if (left == 1) { words = " " + teens[digit] + words; index++; mod /= 10; } else { words = " " + ones[digit] + words; } } else if (index == 1 && digit > 0) { words = " " + tens[digit] + words; } else if (index == 2 && digit > 0) { words = " " + ones[digit] + " Hundred" + words; } index++; mod /= 10; } num /= 1000; if (thousand == 0 && num % 1000 > 0) { words = " Thousand" + words; } else if (thousand == 1 && num % 1000 > 0) { words = " Million" + words; } else if (thousand == 2 && num > 0) { words = " Billion" + words; } thousand++; } return words.trim(); } }

Time complexity:
Say the number has n digits. Consider string concatenation is O(s). The overall time complexity is O(ns).