Number To Words Algorithm

Number To Words Algorithm

Problem: Given any number of maximum 15 digits number convert it to a string which represents this number in words.
e.g., Input: 231 Output: Two Hundred And Thirty One.

1. Input example: 34541009234120

Find length of input string of digits, if it's a multiple of 3 then do nothing else pad with leading zero's to make it's length an exact multiple of 3 and divide the input number into 5 groups of 3 digits each, so our example input becomes

034 541 009 234 120
   Group No.   5   4   3   2   1

2. Find group of most siginificant digit, e.g., here MSD is 0 and it's group is:

groupNum = length%3 ? (length/3+1) : (length/3);

3. One loop for number of groups of 3 digits each;

4. One loop for each of the 3 digits inside a given group, so the time complexity boils down to linear;

5. Inside inner loop, for any given 3 digits generate a string like for e.g., 541 becomes "Five Hundred And Forty One";

6. Now decide which string would come after this according to the group number e.g., here group of 541 is 4 so "Billion" (from D array given above) would be appended to the string generated in step 5;

7. When outer loop finishes, return the string generated for the whole number.
    e.g., "Thirty Four Trillion Five Hundred And Forty One Billion Nine Million Two Hundred And Thirty Four  Thousand One Hundred And Twenty"

Limitations: 
   1. This algorithm generates words according to US number to words system.
   2. It generates words from numbers till 999 trillion 999 billion 999 million
      999 thousand and 999

Source code (C++):  Available on request.
   Post a comment to mention your email ID. You would receive the source code as
   soon as I get the request.

Cheers! 
Rajendra