Integer to English Words

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

For example:

• If num = 123, the output should be "One Hundred Twenty Three".
• If num = 12345, the output should be "Twelve Thousand Three Hundred Forty Five".
• If num = 1234567, the output should be "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven".

Constraints:

• 0 <= num <= 2^31 - 1

Write a function that takes an integer as input and returns a string representing the number in English words. Consider edge cases such as zero, numbers less than 20, and numbers greater than or equal to 1000. Provide examples to demonstrate the correctness of your solution.

class Solution:
    def numberToWords(self, num: int) -> str:
        less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven",
                        "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        thousands = ["", "Thousand", "Million", "Billion"]

        def helper(n):
            if n < 20:
                return less_than_20[n]
            elif n < 100:
                return tens[n // 10] + (" " + less_than_20[n % 10])
            else:
                return less_than_20[n // 100] + " Hundred " + helper(n % 100)

        if num == 0:
            return "Zero"

        result = []
        for i in range(4):
            if num % 1000 != 0:
                result.append(helper(num % 1000) + " " + thousands[i])
            num //= 1000

        return " ".join(result[::-1]).strip()

Explanation:

1. numberToWords(self, num: int) -> str: This is the main function that takes an integer num as input and returns its English words representation.

2. less_than_20: This list stores the English words for numbers from 0 to 19.

3. tens: This list stores the English words for multiples of ten from 20 to 90.

4. thousands: This list stores the English words for powers of thousand (Thousand, Million, Billion).

5. helper(n): This is a helper function that converts a number less than 1000 to its English words representation.

   • If n is less than 20, it returns the corresponding word from less_than_20.
   • If n is less than 100, it returns the corresponding word from tens for the tens place and recursively calls itself for the ones place.
   • If n is greater than or equal to 100, it returns the corresponding word from less_than_20 for the hundreds place, adds "Hundred", and recursively calls itself for the remaining part.

6. Handle Zero: If the input num is 0, it directly returns "Zero".

7. Iterate through thousands: The code iterates through the input number by breaking it into chunks of three digits (less than 1000) using the modulo operator (%). It uses integer division (//=) to move to the next chunk.

8. Build the result: For each chunk, it calls the helper function to convert it to English words and appends the corresponding word from thousands (Thousand, Million, Billion) based on the iteration count.

9. Join and return: Finally, it joins the elements of the result list in reverse order (since we built the result from the least significant part), removes any leading or trailing spaces, and returns the final string.

Example Usage:

sol = Solution()
print(sol.numberToWords(123))  # Output: "One Hundred Twenty Three"
print(sol.numberToWords(12345)) # Output: "Twelve Thousand Three Hundred Forty Five"
print(sol.numberToWords(1234567)) # Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Time and Space Complexity:

• Time Complexity: O(1). The algorithm processes the number in chunks of three digits, and the number of chunks is limited (at most 4 for numbers up to 2^31 - 1). Therefore, the time complexity is constant.

• Space Complexity: O(1). The space used by the algorithm is constant because the size of the lists less_than_20, tens, and thousands does not depend on the input number. The recursion depth of the helper function is also limited, so the space used by the call stack is also constant.

Edge Cases:

1. Zero: The code handles the case when the input number is 0 by returning "Zero".

2. Numbers less than 20: The code correctly handles numbers less than 20 using the less_than_20 list.

3. Numbers between 20 and 99: The code correctly handles numbers between 20 and 99 using the tens list and the less_than_20 list.

4. Numbers between 100 and 999: The code correctly handles numbers between 100 and 999 by extracting the hundreds digit and recursively calling itself for the remaining part.

5. Numbers greater than or equal to 1000: The code correctly handles numbers greater than or equal to 1000 by breaking them into chunks of three digits and appending the corresponding word from the thousands list.

6. Maximum Integer: The code works correctly for the maximum integer value (2^31 - 1) as it handles the billions place correctly.