• Posts

Problem 273 Integer to English Words

Problem Statement

Link - Problem 273

Question

Convert a non-negative integer num to its English words representation.

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Constraints:

• 0 <= num <= 231 - 1

Solution

class Solution {
public:
    string numberToWords(int num) {

        if (num == 0) return "Zero";


        const vector<string> ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        const vector<string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        const vector<string> thousands = {"", "Thousand", "Million", "Billion"};


        string result = "";
        int groupIndex = 0;


        while (num > 0) {
            if (num % 1000 != 0) {
                string groupResult = "";
                int part = num % 1000;

                if (part >= 100) {
                    groupResult = ones[part / 100] + " Hundred ";
                    part %= 100;
                }

                if (part >= 20) {
                    groupResult += tens[part / 10] + " ";
                    part %= 10;
                }

                if (part > 0) {
                    groupResult += ones[part] + " ";
                }

                groupResult += thousands[groupIndex] + " ";

                result = groupResult + result;
            }

            num /= 1000;
            groupIndex++;
        }

        return result.substr(0, result.find_last_not_of(" ") + 1);
    }
};

Complexity Analysis

| Algorithm                            | Time Complexity | Space Complexity |
| ------------------------------------ | --------------- | ---------------- |
| Iterative number to words conversion | O(log n)        | O(log n)         |

Explanation

Intial Thoughts

To solve this problem, we need to break down the number into smaller groups of three digits. We should start with the ones, tens, and hundreds places, and then move to thousands, millions, and billions. We can use arrays to map numbers to their corresponding word representations. It’s also important to handle special cases like zero and numbers that are less than 20. We should think about how to handle the ‘and’ and ‘hundred’ keywords in the word representation.

Intuitive Analysis

Intuitively, we can approach this problem by thinking of it like writing a check. We start with the largest denomination and work our way down. For example, if we have 1234, we would say ‘one thousand two hundred thirty four’. We can use this same logic to build our word representation. We should also think about how to handle numbers that have multiple denominations, like thousands and hundreds. Breaking down the problem into smaller parts and using arrays to map numbers to words can help simplify the solution. We can also use a loop to process each group of three digits.

1. Intuition

• The problem requires converting a non-negative integer to its English words representation, which involves breaking down the number into groups of three digits (thousands, millions, billions) and then converting each group to words.
• To approach this problem, we need to consider the different cases for numbers less than 20, numbers between 20 and 99, and numbers greater than or equal to 100.
• We also need to handle the cases for thousands, millions, and billions by appending the corresponding word to the result.
• The key insight is to use a while loop to process the number in groups of three digits, starting from the least significant group.
• We can use arrays to store the English words for ones, tens, and thousands, making it easier to access and append the correct words to the result.
• The solution works by iteratively processing the number in groups of three digits, converting each group to words, and appending the corresponding thousand, million, or billion word.
• The algorithmic choice of using a while loop and arrays allows for efficient and readable code.

2. Implementation

• We define arrays ones, tens, and thousands to store the English words for ones, tens, and thousands, respectively.
• The while loop is used to process the number in groups of three digits, with the condition num > 0 ensuring that the loop continues until all groups have been processed.
• Inside the loop, we use the modulo operator (num % 1000) to extract the current group of three digits and store it in the part variable.
• We then use conditional statements to convert the part to words, appending the corresponding words from the ones and tens arrays, and the thousands array for the group index.
• The result is built by prepending the converted group to the result string, effectively building the English words representation from right to left.
• Finally, we use the substr function to remove any trailing spaces from the result string before returning it.
• The use of const for the arrays and variables ensures that the code is efficient and easy to read.

Complexity Analysis

Time Complexity:

• The time complexity of the numberToWords function is O(log n) because the while loop runs until num becomes 0, and in each iteration, num is divided by 1000. This is equivalent to the number of digits in the input number, which is log(n) where n is the input number.
• The dominant operation in the function is the while loop, and the number of iterations of the loop determines the time complexity. The operations inside the loop, such as string concatenation and array indexing, take constant time.
• The mathematical reasoning behind this is that the number of digits in a number n is log(n) (base 10), and since we are dividing the number by 1000 in each iteration, we are effectively reducing the number of digits by 3 in each iteration, resulting in O(log n) time complexity.

Space Complexity:

• The space complexity of the numberToWords function is O(log n) because the maximum amount of space used by the function is proportional to the number of digits in the input number.
• The result string and the groupResult string contribute to the space complexity. The length of these strings is at most the number of digits in the input number, resulting in O(log n) space complexity.
• Additionally, the ones, tens, and thousands arrays also contribute to the space complexity, but their size is constant and does not depend on the input size, so they do not affect the overall O(log n) space complexity.

Footnote

This question is rated as Hard difficulty.

Hints

Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.

Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.

There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

Similar Questions: