273. Integer to English Words

Problem Description

The LeetCode problem presented requires the conversion of a non-negative integer num into its English words representation. The task is to write a program that will take any non-negative integer and translate it into the corresponding words as one would read it in English. The algorithm needs to handle the structure of English numbering, including the placement of thousands, millions, and billions, as well as the rules for forming numbers less than one hundred.

Intuition

The solution to converting numbers into their English words representation relies on understanding the pattern and structure of English numbers. We can break down the problem into manageable parts by considering that:

Numbers from 1 to 19 have unique names which do not follow a particular pattern, so we prepare a list for those (lt20).
Tens from 20 to 90 also have distinct names, so we list them out (tens).
Complex numbers are generally combinations of smaller numbers. For example, 345 can be read as "Three Hundred Forty-Five", which combines "Three Hundred" with the smaller number "Forty-Five".
English names for numbers above 99 are formed by appending a scale word like "Thousand", "Million", or "Billion" and then saying the name of the number that follows.

Given this, we approach the problem by creating a recursive function transfer that can handle numbers less than a thousand. We then iteratively apply this function to parts of the input number, working our way from billions down to units, appending appropriate scale terms, and concatenating all parts to form the full English words representation.

To track units of thousand, we maintain an array thousands, which contains scale words each separated by a factor of a thousand, and an adjusted counter to work on portions of the number. Using division and modulo operations, we can slice the number into segments that can be processed by transfer before attaching the corresponding scale term (if any).

The process starts with the largest possible unit, billions, and strips away parts of the number progressively until the entire number has been converted. We then join the formed segments and clean up any extra spaces to get the final English words representation.

Learn more about Recursion and Math patterns.

Solution Approach

The solution implementation begins with setting up the base case for the number zero, returning 'Zero' if num is equal to zero.

Data Structures Used:

lt20: A list containing the English words for numbers 1 through 19.
tens: A list containing the English words for multiples of ten, from 20 to 90.
thousands: A list to denote the scale terms (Billion, Million, Thousand).
res: A list that will accumulate the segments of the word representation.

Algorithm:

A recursive helper function transfer is defined to convert numbers less than 1000 into words:

If num is less than 20, it returns the corresponding word from lt20.
If num is less than 100, it returns the word from tens for the tens place followed by the recursive call for the remainder (num % 10).
For larger numbers, it returns the word for hundreds place from lt20, followed by 'Hundred', and then the recursive call for the remainder of dividing by 100.

The main function works with these steps:

Initialization by checking if the input num is zero, subsequently returning 'Zero'.
A loop is set to iterate through scales (billion to thousand) using variables i and j where i starts at 10^9 and j is index position in thousands.
Inside the loop:
- Check if current segment (num // i) is non-zero.
- If so, call transfer for that segment, and append the result along with the scale term (thousands[j]) to res.
- Use modulo operation num % i to move to the next segment.
- Increment j and divide i by 1000 to proceed to the next lower scale term.
After processing all segments, join the parts in res stripping trailing or duplicate spaces.

Patterns Used:

Divide and conquer: The number is divided into smaller parts, each of which is processed independently (billion, million, thousand, less than a thousand).
Recursion: A recursive function transfer is used to build up the word representation of numbers less than 1000.
Modular arithmetic: Division (num // i) and modulo (num % 10, num % 100, num % i) operations extract specific digits or segments from the number.
Array indexing: Lists lt20, tens, and thousands are accessed via indices to retrieve the English words for numbers and scale terms.

Performance and Complexity:

The algorithm runs in O(n) where n is the number of digits in the input number since each digit or group of digits is processed once. The space complexity is also O(n) due to the storage required for the word representation of the number.

By breaking down the problem into smaller subproblems and following the structure of English number words, the algorithm effectively converts any non-negative integer into its English words counterpart.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take the number 12345 as an example to illustrate the solution approach.

We start by checking if num is zero. Our number isn't zero, so we move to the next step.
We prepare our data structures lt20, tens, and thousands, and an empty list res for accumulating results.
The transfer function is ready to be used, but we start with the scale terms.
We look at our largest unit, billions (10^9). Since 12345 is smaller than one billion, we move to the next scale—millions. It's not a million either, so we proceed to thousands.
We see that our number is greater than 1000, so we process this segment first.
We divide 12345 by 1000, giving us 12 with a remainder. Using transfer, we turn 12 into "Twelve" and append "Thousand" to get "Twelve Thousand". We add this to our res list.
The remainder is now 345, which we process next. It's less than 1000, so the transfer function will handle it directly.
Inside transfer, 345 is not less than 20 or 100, so we further break it down to "Three Hundred" ("Three" from lt20 and "Hundred") and then recursively process 45.
For the number 45, we again call transfer. It's less than 100 but more than 20, so the function returns the corresponding word for the tens place, "Forty", and the word for the ones place, "Five".
We concatenate "Three Hundred" with "Forty-Five" to create "Three Hundred Forty-Five".
We append "Three Hundred Forty-Five" to our res list.
Now our res list is ["Twelve Thousand", "Three Hundred Forty-Five"]. We join these with a space to make the final output: "Twelve Thousand Three Hundred Forty-Five".

We followed the approach, using recursion for numbers under 1000, modular arithmetic to divide the number into manageable segments, and array indexing to map numbers to their respective words. The process broken down into the loop and conditional checks ensures that the number is systematically converted into its English words representation.

Solution Implementation

1class Solution:
2    def numberToWords(self, num: int) -> str:
3        # Check for the zero case explicitly
4        if num == 0:
5            return 'Zero'
6
7        # Words for numbers less than 20
8        less_than_20 = [
9            '', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine',
10            'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen',
11            'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'
12        ]
13      
14        # Tens place words
15        tens = [
16            '', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety'
17        ]
18      
19        # Units of thousand
20        thousands = ['Billion', 'Million', 'Thousand', '']
21
22        # Helper function to convert a number less than 1000 to words
23        def translate(num):
24            if num == 0:
25                return ''
26            elif num < 20:
27                return less_than_20[num] + ' '
28            elif num < 100:
29                return tens[num // 10] + ' ' + translate(num % 10)
30            else:
31                return less_than_20[num // 100] + ' Hundred ' + translate(num % 100)
32
33        result = []  # List to store the parts of the result string
34        i, j = 1000000000, 0  # Initialize the divisor for the highest unit (billion) and the index for units
35      
36        # Loop to handle each unit position from billion down to ones
37        while i > 0:
38            if num // i != 0:
39                result.append(translate(num // i))  # Convert the current unit position to words
40                result.append(thousands[j])         # Add the unit name (Billion, Million, ...)
41                result.append(' ')                  # Add space after the unit name
42                num %= i                            # Update the number, removing the current unit portion
43            j += 1  # Increment the index for units
44            i //= 1000  # Move to the next unit (from billion to million to thousand to ones)
45      
46        return ''.join(result).strip()  # Convert the list to a string and remove any leading/trailing space
47

1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
5    // Static map to hold number to words mapping
6    private static final Map<Integer, String> NUMBER_TO_WORDS_MAP;
7
8    // Static initializer block used to populate the map
9    static {
10        NUMBER_TO_WORDS_MAP = new HashMap<>();
11        // Single digit mappings
12        NUMBER_TO_WORDS_MAP.put(1, "One");
13        NUMBER_TO_WORDS_MAP.put(2, "Two");
14        NUMBER_TO_WORDS_MAP.put(3, "Three");
15        NUMBER_TO_WORDS_MAP.put(4, "Four");
16        NUMBER_TO_WORDS_MAP.put(5, "Five");
17        NUMBER_TO_WORDS_MAP.put(6, "Six");
18        NUMBER_TO_WORDS_MAP.put(7, "Seven");
19        NUMBER_TO_WORDS_MAP.put(8, "Eight");
20        NUMBER_TO_WORDS_MAP.put(9, "Nine");
21        // Teen mappings
22        NUMBER_TO_WORDS_MAP.put(10, "Ten");
23        NUMBER_TO_WORDS_MAP.put(11, "Eleven");
24        NUMBER_TO_WORDS_MAP.put(12, "Twelve");
25        NUMBER_TO_WORDS_MAP.put(13, "Thirteen");
26        NUMBER_TO_WORDS_MAP.put(14, "Fourteen");
27        NUMBER_TO_WORDS_MAP.put(15, "Fifteen");
28        NUMBER_TO_WORDS_MAP.put(16, "Sixteen");
29        NUMBER_TO_WORDS_MAP.put(17, "Seventeen");
30        NUMBER_TO_WORDS_MAP.put(18, "Eighteen");
31        NUMBER_TO_WORDS_MAP.put(19, "Nineteen");
32        // Tens place mappings
33        NUMBER_TO_WORDS_MAP.put(20, "Twenty");
34        NUMBER_TO_WORDS_MAP.put(30, "Thirty");
35        NUMBER_TO_WORDS_MAP.put(40, "Forty");
36        NUMBER_TO_WORDS_MAP.put(50, "Fifty");
37        NUMBER_TO_WORDS_MAP.put(60, "Sixty");
38        NUMBER_TO_WORDS_MAP.put(70, "Seventy");
39        NUMBER_TO_WORDS_MAP.put(80, "Eighty");
40        NUMBER_TO_WORDS_MAP.put(90, "Ninety");
41        // Scale mappings
42        NUMBER_TO_WORDS_MAP.put(100, "Hundred");
43        NUMBER_TO_WORDS_MAP.put(1000, "Thousand");
44        NUMBER_TO_WORDS_MAP.put(1000000, "Million");
45        NUMBER_TO_WORDS_MAP.put(1000000000, "Billion");
46    }
47
48    // Converts a number to words
49    public String numberToWords(int num) {
50        // Special case for zero
51        if (num == 0) {
52            return "Zero";
53        }
54
55        StringBuilder wordsBuilder = new StringBuilder();
56      
57        // Process the number for billions, millions, and thousands
58        for (int i = 1000000000; i >= 1000; i /= 1000) {
59            if (num >= i) {
60                wordsBuilder.append(processThreeDigits(num / i)).append(" ").append(NUMBER_TO_WORDS_MAP.get(i));
61                num %= i;
62            }
63        }
64      
65        // Append the remaining words for numbers less than a thousand
66        if (num > 0) {
67            wordsBuilder.append(processThreeDigits(num));
68        }
69      
70        // Remove the leading space and return the result
71        return wordsBuilder.substring(1);
72    }
73
74    // Helper function to process up to three digits of the number
75    private String processThreeDigits(int num) {
76        StringBuilder threeDigitsBuilder = new StringBuilder();
77      
78        if (num >= 100) {
79            threeDigitsBuilder.append(" ")
80                             .append(NUMBER_TO_WORDS_MAP.get(num / 100))
81                             .append(" ")
82                             .append(NUMBER_TO_WORDS_MAP.get(100));
83            num %= 100;
84        }
85        if (num > 0) {
86            // Direct mapping for numbers less than 20 or multiples of 10
87            if (num < 20 || num % 10 == 0) {
88                threeDigitsBuilder.append(" ").append(NUMBER_TO_WORDS_MAP.get(num));
89            } else {
90                // Combine the tens and ones place for other numbers
91                threeDigitsBuilder.append(" ")
92                                  .append(NUMBER_TO_WORDS_MAP.get(num / 10 * 10))
93                                  .append(" ")
94                                  .append(NUMBER_TO_WORDS_MAP.get(num % 10));
95            }
96        }
97        return threeDigitsBuilder.toString();
98    }
99}
100

1#include <iostream>
2#include <unordered_map>
3#include <string>
4
5// Use 'using' for brevity
6using std::unordered_map;
7using std::string;
8
9class Solution {
10public:
11    // Static map to hold number to words mapping
12    static unordered_map<int, string> number_to_words_map;
13
14    // Static function to initialize the map
15    static void initialize_number_to_words_map() {
16        // Single digit mappings
17        number_to_words_map[1] = "One";
18        number_to_words_map[2] = "Two";
19        // ... (and so on for other single digit mappings)
20      
21        // Teen mappings
22        number_to_words_map[10] = "Ten";
23        // ... (and so on for other teen mappings)
24
25        // Tens place mappings
26        number_to_words_map[20] = "Twenty";
27        // ... (and so on for other tens place mappings)
28
29        // Scale mappings
30        number_to_words_map[100] = "Hundred";
31        number_to_words_map[1000] = "Thousand";
32        number_to_words_map[1000000] = "Million";
33        number_to_words_map[1000000000] = "Billion";
34    }
35
36    // Converts a number to words
37    string numberToWords(int num) {
38        // Special case for zero
39        if (num == 0) {
40            return "Zero";
41        }
42
43        string words = "";
44
45        // Process the number for billions, millions, and thousands
46        for (int i = 1000000000; i >= 1000; i /= 1000) {
47            if (num >= i) {
48                words += processThreeDigits(num / i) + " " + number_to_words_map[i];
49                num %= i;
50            }
51        }
52
53        // Append the remaining words for numbers less than a thousand
54        if (num > 0) {
55            words += processThreeDigits(num);
56        }
57
58        // Trim the leading space and return the result
59        if (!words.empty() && words.front() == ' ') {
60            words = words.substr(1);
61        }
62        return words;
63    }
64
65private:
66    // Helper function to process up to three digits of the number
67    string processThreeDigits(int num) {
68        string result = "";
69
70        if (num >= 100) {
71            result += " " + number_to_words_map[num / 100] + " " + number_to_words_map[100];
72            num %= 100;
73        }
74        if (num > 0) {
75            // Direct mapping for numbers less than 20 or multiples of 10
76            if (num < 20 || num % 10 == 0) {
77                result += " " + number_to_words_map[num];
78            } else {
79                // Combine the tens and ones place for other numbers
80                result += " " + number_to_words_map[num / 10 * 10] + " " + number_to_words_map[num % 10];
81            }
82        }
83        return result;
84    }
85};
86
87// Definition of static member
88unordered_map<int, string> Solution::number_to_words_map;
89
90int main() {
91    // Initialize the static map before using it
92    Solution::initialize_number_to_words_map();
93  
94    Solution sol;
95    std::cout << sol.numberToWords(123) << std::endl; // Output: "One Hundred Twenty Three"
96    std::cout << sol.numberToWords(12345) << std::endl; // Output: "Twelve Thousand Three Hundred Forty Five"
97    // ... Test with additional cases
98
99    return 0;
100}
101

1// Map to hold number to words mapping
2const numberToWordsMap: { [key: number]: string } = {
3  // Single digit mappings
4  1: 'One',
5  2: 'Two',
6  3: 'Three',
7  4: 'Four',
8  5: 'Five',
9  6: 'Six',
10  7: 'Seven',
11  8: 'Eight',
12  9: 'Nine',
13  // Teen mappings
14  10: 'Ten',
15  11: 'Eleven',
16  12: 'Twelve',
17  13: 'Thirteen',
18  14: 'Fourteen',
19  15: 'Fifteen',
20  16: 'Sixteen',
21  17: 'Seventeen',
22  18: 'Eighteen',
23  19: 'Nineteen',
24  // Tens place mappings
25  20: 'Twenty',
26  30: 'Thirty',
27  40: 'Forty',
28  50: 'Fifty',
29  60: 'Sixty',
30  70: 'Seventy',
31  80: 'Eighty',
32  90: 'Ninety',
33  // Scale mappings
34  100: 'Hundred',
35  1000: 'Thousand',
36  1000000: 'Million',
37  1000000000: 'Billion',
38};
39
40/**
41 * Converts a number to words.
42 *
43 * @param {number} num - The number to be converted to words.
44 * @returns {string} - The corresponding words representing the number.
45 */
46function numberToWords(num: number): string {
47  // Special case for zero
48  if (num === 0) {
49    return 'Zero';
50  }
51
52  let wordsBuilder: string = '';
53
54  // Process the number for billions, millions, and thousands
55  for (let i: number = 1000000000; i >= 1000; i /= 1000) {
56    if (num >= i) {
57      wordsBuilder += ` ${processThreeDigits(Math.floor(num / i))} ${numberToWordsMap[i]}`;
58      num %= i;
59    }
60  }
61
62  // Append the remaining words for numbers less than a thousand
63  if (num > 0) {
64    wordsBuilder += processThreeDigits(num);
65  }
66
67  // Remove the leading space and return the result
68  return wordsBuilder.trim();
69}
70
71/**
72 * Helper function to process up to three digits of a number.
73 *
74 * @param {number} num - The number (less than 1000) to process.
75 * @returns {string} - The words representing the three digits.
76 */
77function processThreeDigits(num: number): string {
78  let threeDigitsBuilder: string = '';
79
80  if (num >= 100) {
81    threeDigitsBuilder += ` ${numberToWordsMap[Math.floor(num / 100)]} ${numberToWordsMap[100]}`;
82    num %= 100;
83  }
84  if (num > 0) {
85    // Direct mapping for numbers less than 20 or multiples of 10
86    if (num < 20 || num % 10 === 0) {
87      threeDigitsBuilder += ` ${numberToWordsMap[num]}`;
88    } else {
89      // Combine the tens and ones place for other numbers
90      threeDigitsBuilder += ` ${numberToWordsMap[Math.floor(num / 10) * 10]} ${numberToWordsMap[num % 10]}`;
91    }
92  }
93  return threeDigitsBuilder.trim();
94}
95

Time and Space Complexity

Time Complexity

The time complexity of this function is primarily influenced by the division and modulo operations inside the while loop. The loop itself is executed a constant number of times (4 iterations, one for each group of digits corresponding to "Billion", "Million", "Thousand", and the sub-thousand level). Each iteration involves constant-time arithmetic operations and a recursive call to the transfer function, which has a worst-case scenario of constant time (since numbers less than 1000 are processed directly, with at most two recursive calls for numbers <100).

Therefore, the overall time complexity is O(1), as it does not scale with the input number.

Space Complexity

The space complexity is largely governed by the storage of intermediate string results and the use of recursion for numbers less than 1000. However, the depth of recursion does not exceed a constant (with a maximum recursion depth = 3 for numbers less than 1000). The array res holds a fixed number of strings corresponding to the digit group labels and their English representations.

Consequently, the space complexity is also O(1) since the algorithm allocates a constant amount of additional space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know