Problem Explanation

This problem is asking us to convert a non-negative integer to its English words representation.

Let's look at an example,

For instance, if the input is 123, the expected output is "One Hundred Twenty Three". When we look at the input 12345, the expected output is "Twelve Thousand Three Hundred Forty Five".

Our task is to take any non-negative integer less than 2^31 -1 and return its English words representation as a string.

Approach

To solve this problem, we need to break down the given numbers into parts and handle their conversion separately. The parts defined are:

• Numbers below twenty ( because these have unique names)
• Numbers from twenty to ninety-nine (have a unique name for each ten then add number below 20 if any)
• Numbers from one hundred to nine hundred ninety (from 100 every the integer number is represented in hundred + tens )
• Numbers from one thousand to ninety-nine thousand nine hundred ninety-nine (from 1k every integer is represented in thousand + hundreds + tens)
• Numbers from one million to one billion (follow same principle but start with million and billion)

Solution walk through

Our approach to solve the problem is to implement a recursive helper method that will take in the number and do the conversion.

Let's take an example num = 1234567.

The steps are:

1. Check if num is less than 20, it's not, go to the next step.
2. Check if num is less than 100, it's not, go to the next step.
3. Check if num is less than 1000, it's not, go to the next step.
4. Check if num is less than 1000000, it is, so call helper(num/1000) + " Thousand " + helper(num%1000), the last part is to ensure we handle the numbers less than 1000 in our number. At this point, num/1000 = 1234, helper(num%1000) => helper(567).
5. We call the helper method again with 1234 and 567, following the same steps
6. Eventually we'll have "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" which is the correct output.

We also define two lists, one to hold the words representation for numbers below 20 (each number below 20 has a unique name) and another for tens (each tens number from 20 to 90 has its unique name).

There's also a method to remove any trailing or leading spaces which we call at the end.

That's the gist of our algorithm. Let's now look at example solutions using Python, Java, JavaScript, C++, and C#.

Python solution

Here is the code in Python, with explanatory comments,

1
2python
3class Solution:
4    def numberToWords(self, num: int) -> str:
5        to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
6               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
7        tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
8        def words(n):
9            if n < 20:
10                return to19[n-1:n] # 
11            if n < 100:
12                return [tens[n//10-2]] + words(n%10)
13            if n < 1000:
14                return [to19[n//100-1]] + ['Hundred'] + words(n%100)
15            for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
16                if n < 1000**(p+1):
17                    return words(n//1000**p) + [w] + words(n%1000**p)
18        return ' '.join(words(num)) or 'Zero'

This Python solution checks if the number is smaller than 20, and if it is, it returns the corresponding word from the to19 array. If it's less than 100, it calculates the index of the corresponding tens word by dividing the number by 10 and subtracting 2. It also recursively processes the remaining part of the number (n%10). Similarly, if it's less than 1000, it computes the hundreds part and recurses on the tens part. Finally, for bigger numbers, it finds the appropriate unit ('Thousand', 'Million', or 'Billion') and recurses on the parts before and after that unit. In all cases, it returns a list of words which gets joined by spaces to form the final result.

JavaScript Solution

1
2javascript
3var numberToWords = function(num) {
4    if (num === 0) return 'Zero';
5
6    const toTwenty = ['','One','Two','Three','Four', 'Five','Six','Seven','Eight','Nine','Ten','Eleven',
7                      'Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen'];
8    const tens = ['', '', 'Twenty','Thirty','Forty','Fifty', 'Sixty','Seventy','Eighty','Ninety'];
9    const thousands = ['', 'Thousand','Million','Billion'];
10
11    let result = '', index = 0;
12    
13    while (num > 0) {
14        if (num % 1000 !== 0) 
15            result = helper(num % 1000) + thousands[index] + ' ' + result;
16        
17        num = Math.floor(num / 1000);
18        index++;
19    }
20    
21    return result.trim();
22
23    function helper(n) {
24        if (n === 0) 
25            return '';
26        else if (n < 20)
27            return toTwenty[n] + ' ';
28        else if (n < 100)
29            return tens[Math.floor(n / 10)] + ' ' + helper(n % 10);
30        else
31            return toTwenty[Math.floor(n / 100)] + ' Hundred ' + helper(n % 100);
32    }
33};

The JavaScript solution here is very similar to the Python solution. It also uses a helper function to convert parts of the number to words, and computes the thousands, millions, and billions parts in a while loop. The result is concatenated with each recursive call of the helper function on the remainder of the number.

Java Solution

Here is the corresponding Java solution:

1
2java
3class Solution {
4    private static final String[] below20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", 
5                                             "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
6                                             "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
7    private static final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", 
8                                           "Seventy", "Eighty", "Ninety"};
9    private static final String[] thousands = {"", "Thousand", "Million", "Billion"};
10    
11    public String numberToWords(int num) {
12        if (num == 0) return "Zero";
13        
14        int i = 0;
15        String result = "";
16        
17        while (num > 0) {
18            if (num % 1000 != 0)
19                result = helper(num % 1000) + thousands[i] + " " + result;
20            
21            num /= 1000;
22            i++;
23        }
24        
25        return result.trim();
26    }
27    
28    private String helper(int n) {
29        if (n == 0) 
30            return "";
31        else if (n < 20)
32            return below20[n] + " ";
33        else if (n < 100)
34            return tens[n / 10] + " " + helper(n % 10);
35        else 
36            return below20[n / 100] + " Hundred " + helper(n % 100);
37    }
38}

The Java code is very similar to the JavaScript solution with the use of helper function to process parts of the number recursively. The main difference is that Java uses a for loop and modulus operator to split the number into thousands, millions, and billions parts. It then appends each part to the result string.