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.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
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
numis less than 20, it returns the corresponding word fromlt20. - If
numis less than 100, it returns the word fromtensfor 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
numis zero, subsequently returning 'Zero'. - A loop is set to iterate through scales (billion to thousand) using variables
iandjwhereistarts at 10^9 andjis index position inthousands. - Inside the loop:
- Check if current segment (
num // i) is non-zero. - If so, call
transferfor that segment, and append the result along with the scale term (thousands[j]) tores. - Use modulo operation
num % ito move to the next segment. - Increment
jand divideiby 1000 to proceed to the next lower scale term.
- Check if current segment (
- After processing all segments, join the parts in
resstripping 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
transferis 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, andthousandsare 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.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Example Walkthrough
Let's take the number 12345 as an example to illustrate the solution approach.
- We start by checking if
numis zero. Our number isn't zero, so we move to the next step. - We prepare our data structures
lt20,tens, andthousands, and an empty listresfor accumulating results. - The
transferfunction 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 ourreslist. - The remainder is now 345, which we process next. It's less than 1000, so the
transferfunction will handle it directly. - Inside
transfer, 345 is not less than 20 or 100, so we further break it down to "Three Hundred" ("Three" fromlt20and "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
reslist. - Now our
reslist 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
471import 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}
1001#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}
1011// 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}
95What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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.
Which type of traversal does breadth first search do?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.