Integer To English Words - Leetcode Solution

Problem Statement:

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"

Example 4: Input: num = 0 Output: "Zero"

Solution:

The problem is to convert a non-negative integer to its English words representation. To solve this problem, we can break it down into smaller parts and use recursion to solve it. We will create a function that takes a number and returns its English word representation.

Step 1: Create a list of strings that contains the numbers from 0 to 19 and all the multiples of ten up to 90.

num_str = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]

tens_str = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]

Step 2: Create a function num_to_word that takes a number and returns its English word representation.

def num_to_word(n: int) -> str: if n < 20: return num_str[n] elif n < 100: return tens_str[n//10] + " " + num_str[n%10] if n%10 != 0 else tens_str[n//10] elif n < 1000: return num_str[n//100] + " Hundred " + num_to_word(n%100) if n%100 != 0 else num_str[n//100] + " Hundred" elif n < 1000000: return num_to_word(n//1000) + " Thousand " + num_to_word(n%1000) if n%1000 != 0 else num_to_word(n//1000) + " Thousand" elif n < 1000000000: return num_to_word(n//1000000) + " Million " + num_to_word(n%1000000) if n%1000000 != 0 else num_to_word(n//1000000) + " Million" else: return num_to_word(n//1000000000) + " Billion " + num_to_word(n%1000000000) if n%1000000000 != 0 else num_to_word(n//1000000000) + " Billion"

Step 3: In the main function, call the num_to_word function with the given input integer.

def numberToWords(num: int) -> str: if num == 0: return "Zero" else: return num_to_word(num)

Time Complexity:

The time complexity of the above solution is O(log n) since we are dividing the input number by 10 at each recursive call.

Space Complexity:

The space complexity of the above solution is O(1) since we are using a fixed amount of memory to store the strings. The recursive function call stack will take additional space, but it is proportional to the number of digits in the input number and therefore can be considered O(log n).

1