Contents

1 Problem Statement

Please refer to the word numbers problem on this page.

2 Download and install the code

Before I even explain how I tried to solve this problem, you can download and install the code from my bitbucket word-nums repository.

After you have tried finding numbers and are convinced that this application does solve the problem, if you are interested in understanding the details of the solution, you may continue reading.

3 Analysis

The characteristics of the problem are:

• A collection of numbers sorted by their word equivalent
• We need to look up a number by the number of letters counted while reaching that number in the sorted list
• An extremely large input of 1 billion numbers

Thus while we build the collection of numbers, if we can keep the collection sorted and as a next step, compute the number of letters ’l’ covered while reaching a number in the sorted list, we can then use ’l’ as an index into the sorted collection. The collection then is a data structure with the requirements of fast inserts and queries, which is a binary search tree. Since we have an index to maintain, an indexed B-Tree will be a good choice of data structure. Thankfully, a B-Tree is also useful when the input is large, which is true in our case, but that does not imply we will not attempt an elegant solution simply because brute force might as well work here.

Finally, we first need to convert a given number into its word equivalent. The algorithm to do the conversion is described next.

4 Converting a number into its word equivalent

It can be observed that any number is a repetitive pattern of 1 to 999, scaled by thousand for the next pattern and by million for the next and so on. In our case, we scale only upto millions. Thus it would suffice to generate a word equivalent of a 3 digit number between 1 and 999 and use the scaling factor of thousand and million based upon the number of times the pattern is repeated.

Further for a 3 digit number, any digit that occurs in unit’s or hundred’s place is a simple look up from the numeric form of the digit to its word form. However the translations for the digit in ten’s place are best described as quirky as 1 in ten’s place means ten if followed by 0 in units place, 11 if followed by 1 and so on. The digits 2 to 9 in ten’s place are less quirkier as the conversion depends only on the digit and not by the digit in unit’s place as is the case for 1 in ten’s place.

Thus,it is now possible to generate word equivalent for any number by splitting it into patterns matching a 3 digit number and using the appropriate scale such as thousand and million.

The code that generates a word equivalent is shown here.

5 How about brute force?

Having identified that an index b-tree is a suitable data structure for our needs, and we have already figured out the generation of a word equivalent, it would be straightforward to generate an index b-tree of billion numbers. We can then traverse the tree in sorted order to update the index which is the number of letters covered. Then a simple lookup using the index should suffice.

However this approach will suffer from the problem of time to build an index, sorted b-tree as we have a billion numbers. The time is dependent upon the processing power and memory availabe on the machine that builds the data structure. Of course, we could use a large number of machines (or multiple cores) so that we can build the data structure faster. Even in that case, we still have to ensure that we distribute the numbers evenly between the machines so that all parallel computations complete around the same time!

But would there not be an elegant way out? It turns out, there is!

6 Elegant way out

We have already identified that there is a repititive pattern of digits. We used this property to generate a word equivalent. Then the same property should be helpful in lexicographical ordering of the words. Is this true? Let us find out.

If we sort just the first 999 numbers, the sorted list (A) looks something as shown below:

.

Now consider the numbers upto 999,999. These are actually a group of 999 numbers where each group starts with [1000;2000;3000;999,000]. Their word equivalents are [onethousand,twothousand,threethousand,..,ninehundredninetyninethousand]. These word equivalents can be generated by adding the suffix ’thousand’ to the word equivalents of numbers from 1 to 999, which is our pattern (building block). So the sort order for the numbers upto 999,999 remains the same when expressed as a group of numbers as described above. Further each such group contains an additonal 999 numbers, which happen to be 1 to 999. The same argument holds true for numbers upto 1 billion. Just that a group in this case will contain 1 million numbers.

Overall the three sorted lists A, B, C respectively of multiples of one, thousand and million are shown below.

.

Since any number is either a million or thousand or hundred, we just need to know the lexicographical position of the successive scales starting from the highest scale. Thus for a number that is multiple of million, I need to find out the sorted order position of the millionth part of the number, followed by that for the thousandth part and then for the hundredth part.

As we have a billion numbers to look at, we need to maintain the following 3 databases:

• A database of all the numbers that represent a multiple of one, thousand and million, denoted as {m}_{db}.
• A database of all the numbers that represent a multiple of one and thousand, denoted as {t}_{db}.
• A database of all the numbers that represent a multiple of one, denoted as {o}_{db}.

These databases are shown visually below, in terms of A, B, C above.

.

Now if we can precompute the number of letters counted and the sum, we can have an elegant solution to our problem.

7 Precomputing the sum and number of letters

Since we know the word equivalent of a number, we also know its length. For a number that represents a multiple of one, its length can be denoted as: {l}_{i} A number that is multiple of 1 is the smallest scale and we need to look no further. So the overall sum of all letters in word equivalents of numbers that are multiple of 1 can be represented as:

Now lets consider a number that represents a multiple of thousand. Let the length of its word equivalent be denoted by {l}_{t}. Since such a group contains further 1000 numbers, the length for the group can be described as:

So the total number of letters covered upto 1 million can be denoted as

Similary for a multiple of millions, the formula is:

Here we do not need to compute the overall summation as we are scaling only upto a billion.

On the same lines, the sum of numbers covered can also be computed.

{s}_{thousand} ={\mathop{ \mathop{∑ }}\nolimits }_{i=1}^{999}i

{s}_{million} ={\mathop{ \mathop{∑ }}\nolimits }_{i=1}^{999999}i

{s}_{tg} = t + {s}_{thousand}

where t = (1000 or 2000 or ... 999000)

{s}_{mg} = m + {s}_{million}

where m = (1000,000 or 200,000 or 999,000)

8 Algorithm

Now we can describe the entire algorithm. As a first step, we build the 3 databases which contains the multiples of one, thousand and million. Each database is an indexed btree. Next we update the btree which contains the multiples upto million with the sum and letters covered using the formuale described in the previous section.

Now given the number of letters covered, which is actually an index into our database, we look up the number starting with the millions database using this index. We find the first node n in the btree such that for this node n, if index is {k}_{found},

If {k}_{found} is index, we have found our number. Else, we navigate to the previous node in the tree and check if that is the node we are looking for by computing the number of letters covered. Otherwise, this node forms a part of number and serves as a key into the next database, which is thousands database if it is multiple of thousand or one’s database. Before searching in the next database, we update that database with the letters and sums on each node, as the key is a prefix to each number in the next database.

Every node of the binary tree contains the following data:

• The number n
• The word equivalent of the number n
• The sum of numbers upto n when traversed in sorted order
• The total number of letters covered upto n when traversed in sorted order

This is the code that creates the btrees, and finds an integer.

A visual depiction of the algorithm is shown below.

.

8.1 Efficiency

Since we use an indexed B-Tree, the efficiency of the algorithm while creating and updating a btree is:

while looking up the number is

. Hence the overall efficency is:

9 Disclaimers

The solution is tested on SBCL 1.0.39 on Mac OS X 10.6 using cl-elephant as the btree implementation. I would like to emphasize that the solution was not generated in the sequence described above. I did some detailed whiteboarding and tried out code snippets and finally figured out the solution.

Further, the solution uses only

nodes. So an in-memory version of a binary search tree should as well suffice. Since I had a ready to use disk based indexed B-Tree implementation, I chose to use that.

This is more of a detailed description of the final design rather the process of arriving at the design.

10 Whiteboards

The whiteboard screenshots are shown below.

.

11 What is the number at 51 billionth letter

As per my solution, there is no number that ends at 51 billion. In fact, there is a number that ends at 51 billion and one. And that number is 676465328.

The sum of numbers upto that point is 206392395198132239862723. From the code run at REPL: