# Leetcode:273 Integer to English Words

**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"

**Example 4:**

**Input:** num = 1234567891

**Output:** "One **Billion** Two *Hundred* Thirty Four Million Five *Hundred* Sixty Seven **Thousand** Eight *Hundred* Ninety One"

You may have noticed I have highlighted a few keywords in the examples. Try to look for some sort of pattern before you proceed.

# Intuition

I must need some sort of mapping for unique identifiers like :

# All the words that describe numbers less than 20

one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen# All the words that describe multiples of ten

ten, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety# All the words that describe powers of 10

hundred, thousand, million, billion

**Realization 1 **: At a high level we can figure out the scale of number i.e thousand, million and billion easily.

**Realization 2** : In the examples, you will notice a repeating pattern. If we have a function that converts numbers upto a 100 to words for us, we can reuse the logic for subsequent combinations.

# Solution :

class Solution:

def construct(self):

self.under_nineteen = "Zero, One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Eleven,"\

"Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen".split(',')

self.tens = ", Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety".split(",")

self.thousand = ", Thousand, Million, Billion".split(",")

def helper(self, number):

if number == 0:

return ""

elif number < 20:

return self.under_nineteen[number].strip() + " "

elif number < 100:

return self.tens[number//10].strip() + " " + self.helper(number%10)

else:

return self.under_nineteen[number//100].strip() + " Hundred " + self.helper(number%100)def numberToWords(self, num: int) -> str:

if num == 0:

return "Zero"

ans = ""

# construct provides us with a list of words

self.construct()

# as we continue to loop over a number, we start with the smallest thousands varation

# and go all the way till billion

for item in range(len(self.thousand)):

# the modulo by 1000 helps get numbers in the set of 3

# if number = 1234567890

# iteration 1 : number%1000 = 890

# iteration 2 : number%1000 = 567

if num % 1000 != 0:

ans = self.helper(num%1000) + self.thousand[item].strip() + " " + ans

num //= 1000

return ans.strip()

Runtime : 32 ms , Space : 14.2 MB

Time Complexity : O(N)

We use concatenate ‘+’ here which means everytime the entire length of the string is iterated over. We can further optimize this by using “”.join() instead of string concatenation.

Space Complexity : O(1)

**Optimized Solution :**

class Solution:

def construct(self):

self.under_nineteen = "Zero, One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Eleven,"\

"Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen".split(',')

self.tens = ", Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety".split(",")

self.thousand = ", Thousand, Million, Billion".split(",")

def helper(self, number):

if number == 0:

return ""

elif number < 20:

return "".join([self.under_nineteen[number].strip() + " "])

elif number < 100:

return "".join([self.tens[number//10].strip()," ",self.helper(number%10)])

else:

return "".join([self.under_nineteen[number//100].strip()," Hundred ",self.helper(number%100)])def numberToWords(self, num: int) -> str:

if num == 0:

return "Zero"

ans = ""

# construct provides us with a list of words

self.construct()

# as we continue to loop over a number, we start with the smallest thousands varation

# and go all the way till billion

for item in range(len(self.thousand)):

# the modulo by 1000 helps get numbers in the set of 3

# like if number = 1234567890

# iteration 1 : number%1000 = 890

# iteration 2 : number%1000 = 567

if num % 1000 != 0:

ans = "".join([self.helper(num%1000),self.thousand[item].strip()," ",ans])

num //= 1000

return ans.strip()

Runtime : 24 ms, Space : 14.2 MB