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"

Write a function that takes a non-negative integer as input and returns its English words representation. The input number will be between 0 and 2³¹ - 1.

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]) if n % 10 else tens[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:

The solution converts a non-negative integer into its English words representation. It uses helper arrays to store the string representations of numbers less than 20, tens, and thousands. The helper function converts numbers less than 1000 into words. The main function iterates through the number in chunks of 1000, converting each chunk into words and appending the appropriate magnitude (thousand, million, billion).

Example Usage:

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

Naive Solution:

A naive solution would involve using a large number of if and elif statements to handle each possible number range. This would be very verbose and difficult to maintain.

Optimal Solution:

The provided solution is an optimal solution as it breaks down the problem into smaller subproblems that can be solved recursively. This makes the code more readable and easier to maintain.

Big(O) Run-Time Analysis:

The time complexity is O(1) because the input number is at most 2^31 - 1, meaning the loop in the numberToWords function iterates at most 4 times, and the helper function also takes constant time as it deals with numbers less than 1000.

Big(O) Space Usage Analysis:

The space complexity is O(1) because the space used by the less_than_20, tens, and thousands arrays is constant, regardless of the input number.

Edge Cases:

1. Zero: The code handles the case where the input is 0 by returning "Zero".
2. Numbers less than 20: The code correctly handles numbers less than 20 using the less_than_20 array.
3. Numbers between 20 and 99: The code correctly handles numbers between 20 and 99 using the tens array and the less_than_20 array.
4. Numbers between 100 and 999: The code correctly handles numbers between 100 and 999 by combining the less_than_20 array and the helper function.
5. Numbers greater than 999: The code correctly handles numbers greater than 999 by iterating through the number in chunks of 1000 and appending the appropriate magnitude.