This approach utilizes recursion to convert the integer into segments of hundreds, thousands, millions, and billions, and then converts each of these segments into words using a predefined dictionary. This method divides and conquers the problem by handling one segment at a time.
Time Complexity: O(1), since the number of segments is constant. Space Complexity: O(1), due to constant space usage for building the output string.
1def numberToWords(num):
2 if num == 0:
3 return 'Zero'
4
5 below_20 = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
6 tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
7 thousands = ['', 'Thousand', 'Million', 'Billion']
8
9 def helper(n):
10 if n == 0:
11 return []
12 elif n < 20:
13 return [below_20[n]]
14 elif n < 100:
15 return [tens[n // 10]] + helper(n % 10)
16 else:
17 return [below_20[n // 100]] + ['Hundred'] + helper(n % 100)
18
19 res = []
20 for i, thousand in enumerate(thousands):
21 if num % 1000 != 0:
22 res = helper(num % 1000) + [thousand] + res
23 num //= 1000
24
25 return ' '.join([word for word in res if word])This Python solution decomposes the number recursively into segments of 1000 using integer division and modulus operations. The function helper converts numbers below 1000 to words. The main function iterates over increasing powers of thousand, converts each segment, and concatenates them with appropriate thousand scales.
An iterative approach using a stack can sequentially build the English words representation by handling one segment of the number at a time. This non-recursive method is useful in avoiding too deep recursion especially with large numbers.
Time Complexity: O(1), as the number of operations is fixed for a constant set of segments. Space Complexity: O(1), using constant space for string manipulation.
1var numberToWords = function(num) {
2 if (num === 0) return 'Zero';
3
4 var below20 = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'];
5 var tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety'];
6 var thousands = ['', 'Thousand', 'Million', 'Billion'];
7
8 var helper = function(n) {
9 if (n === 0) return '';
10 else if (n < 20) return below20[n] + ' ';
11 else if (n < 100) return tens[Math.floor(n / 10)] + ' ' + helper(n % 10);
12 else return below20[Math.floor(n / 100)] + ' Hundred ' + helper(n % 100);
13 };
14
15 var words = '';
16 for (var i = 0, unit = 1000; num > 0; i++, num = Math.floor(num / unit)) {
17 if (num % unit !== 0) {
18 words = helper(num % unit) + thousands[i] + ' ' + words;
19 }
20 }
21 return words.trim();
22};This JavaScript solution uses iteration and a helper function to convert each segment of the number into English words. Similar to the recursive solution, it iteratively processes segments in the order of ones, thousands, millions, and so on. This approach uses string concatenation and avoids recursion depth issues.
This approach breaks down the number into smaller chunks of thousands and recursively converts each chunk into words. By handling different magnitudes separately, such as thousands, millions, etc., the problem becomes more manageable.
Time Complexity: O(log(num)) - Because the number is processed in chunks of thousands.
Space Complexity: O(log(num)) - Due to the recursion stack when handling each chunk.
1class Solution:
2 def numberToWords(self, num: int) -> str:
3 to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
4 tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
5 thousands = 'Thousand Million Billion'.split()
6
7 def words(n):
8 if n < 20:
9 return to19[n-1:n]
10 if n < 100:
11 return [tens[n//10-2]] + words(n%10)
12 if n < 1000:
13 return [to19[n//100-1]] + ['Hundred'] + words(n%100)
14 for p, w in enumerate(thousands, 1):
15 if n < 1000**(p+1):
16 return words(n//1000**p) + [w] + words(n%1000**p)
17
18 return ' '.join(words(num)) or 'Zero'This solution uses recursion to handle chunks of up to three digits: ones, tens, and hundreds, separately. It utilizes lists to map integer values to their corresponding English word equivalents for numbers up to nineteen, tens, and big chunks (thousands, millions, billions). When a chunk is processed, it concatenates the word value, and processes recursively for larger chunks.
This approach uses an iterative method to convert the integer into words by dividing the number into parts less than 1000 and mapping each part to its English equivalent. The algorithm keeps updating the resultant string by concatenating appropriate word segments.
Time Complexity: O(log(num)) - Efficient handling by breaking number into segments.
Space Complexity: O(1) - Iterative approach minimizes auxiliary space usage.
1public class Solution {
2 private final String[] below20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
3 private final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
4 private final String[] thousands = {"", "Thousand", "Million", "Billion"};
5
6 public String numberToWords(int num) {
7 if (num == 0) return "Zero";
8
9 String words = "";
10 int i = 0;
11
12 while (num > 0) {
13 if (num % 1000 != 0)
14 words = helper(num % 1000) + thousands[i] + " " + words;
15 num /= 1000;
16 i++;
17 }
18
19 return words.trim();
20 }
21
22 private String helper(int num) {
23 if (num == 0)
24 return "";
25 else if (num < 20)
26 return below20[num] + " ";
27 else if (num < 100)
28 return tens[num / 10] + " " + helper(num % 10);
29 else
30 return below20[num / 100] + " Hundred " + helper(num % 100);
31 }
32}The solution involves converting each part of the number separated by thousands into words iteratively. It uses arrays to map numbers to words, efficiently processing up to two-digit numbers, and recursively handling hundreds, enhancing both clarity and performance.