## Project Euler Problem 17 Solution

##### Convert numbers to words

by {BetaProjects} | MAY 17, 2009 | Project Euler### Project Euler Problem 17 Statement

Give a number, 0 ≤ N ≤ 10^{12}, write out the equivalent value in English. This differs substantially from the original Project Euler problem by adapting it to the HackerRank requirements.

### Solution

#### The intrinsic data

We create several lists to define all the English words that are required to spell any value less than one quintillion. Lists `ones`

and `tens`

are permuted using the `itertools.product`

function to generate the decades and compound numbers between 20 and 99. The words for the numbers 1 through 19 are then prepended to this list and stored in the `units`

list.

You can extend the maximum value by simply adding other magnitudes to the `thousands`

list.

#### The recursive function for hundreds

No matter how big the number is, it can be expressed by translating each 3-digit magnitude to a hundred designation (0-999) and then appending the appropriate thousand's name to the end. For example, consider the number 194,382,426,112 expressed in English:

**One Hundred Four** Billion **Three Hundred Eighty-Two** Million **Four Hundred Twenty-Six** Thousand **One Hundred Twelve**

This pattern in large numbers allows us to create a recursive function (which could easily be replaced by a loop) to call upon itself until all the 3-digit magnitudes are processed. The `q[]`

list will accumulate the word groups for each magnitude. Because we start with the lowest magnitude and work upwards, the list is joined in reverse order and separated by a `space`

for each magnitude.

Here is a flow chart to better explain the logic used to solve this problem:

#### HackerRank version

### Python Source Code

```
import itertools
ones = ['', 'One','Two','Three','Four','Five','Six','Seven','Eight','Nine']
teens = ['Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
tens = ['Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
units = ones + teens + list(map(lambda n: n[0]+("-"+n[1] if n[1] else ''), itertools.product(tens,ones)))
thousands = ['','Thousand','Million','Billion','Trillion','Quadrillion']
def n2words(n, z=0, q=[]):
if n==0: return ' '.join(q[::-1])
n,r = divmod(n, 1000)
if r>0:
h,u = divmod(r, 100)
words = (ones[h]+' Hundred ' if h>0 else '') + units[u] + " " + thousands[z]
q.append(words)
return n2words(n, z+1, q)
n = int(input("Enter a number to spell out? "))
print ('Zero' if n==0 else n2words(n))
```

### Last Word

Other thousands groups: Quintillion 10^{18}, Sextillion 10^{21}, Septillion 10^{24}, Octillion 10^{27}, and even more here.