Project Euler

Problem 17: Number Letter Counts

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

The Catch

How to efficiently calculate the number of letters of 1,000 numbers when they are spelled out.

The Light

The number Divide 1,000 numbers into groups based on the similarity of their spellings:

• 1 - 20
• 21 - 99
• 100 - 999

Reuse the result of previous groups on the latter groups. For example, 128 (one hundred twenty eight) can use 1 (one) from the first group and 28 (twenty eight) from the second group.

The Code

public class Problem17
{
  public static void main(String[] args)
  {
    String[] arr1 = new String[99];
    int arr1Index = 0;

    String[] singleD = {"one", "two", "three", "four", "five", 
                        "six", "seven", "eight", "nine"};

    String ten = "ten";
    String eleven = "eleven";
    String twelve = "twelve";
    String thirteen = "thirteen";
    String fifteen = "fifteen";
    String eighteen = "eighteen";
    String teen = "teen";

    String ty = "ty";
    String twenty = "twenty";
    String thirty = "thirty";
    String forty = "forty";
    String fifty = "fifty";
    String eighty = "eighty";
    String[] tens = new String[8];
    for(int j = 0; j < tens.length; j++)
    {
      if(j == 0) 
      {
        tens[j] = twenty;
        continue;
      }
      if(j == 1)
      {
        tens[j] = thirty;
        continue;
      }
      if(j == 2)
      {
        tens[j] = forty;
        continue;
      }
      if(j == 3)
      {
        tens[j] = fifty;
        continue;
      }
      if(j == 6)
      {
        tens[j] = eighty;
        continue;
      }
      tens[j] = singleD[ j + 1] + ty;
    }

    String and = "and";
    String hundred = "hundred";

    //PRINT OUT THE NUMBERS 1- 20
    for(int i = 1; i <= 20; i++)
    { 
      if(i < 10)
        arr1[arr1Index++] = singleD[i - 1];

      if(i >= 10 && i <= 20)
        switch(i)
        {
          case 10: arr1[arr1Index++] = ten;
                   break;
          case 11: arr1[arr1Index++] = eleven;
                   break;
          case 12: arr1[arr1Index++] = twelve;
                   break;
          case 13: arr1[arr1Index++] = thirteen;
                   break;
          case 15: arr1[arr1Index++] = fifteen;
                   break;
          case 18: arr1[arr1Index++] = eighteen;
                   break;
          case 20: arr1[arr1Index++] = twenty;
                   break;
          default: arr1[arr1Index++] = (singleD[i - 10 - 1] + teen);
                   break;
        }		
    }

    //PRINT OUT NUMBER 21 - 99
    for(int x = 21, index = 0, sIndex = 0; x <= 99; x++)
    { 	 
      if(x % 10 == 0)
      {
        arr1[arr1Index++] = tens[x/10 - 2] ;
        continue;
      }

      if(x > 40 && x < 50)
      {
        arr1[arr1Index++] = "forty" + singleD[sIndex++];
        if(sIndex > 8 && index < 8)
        {
          sIndex = 0;
          index++;
        }
        continue;
      }

      if(x > 80 && x < 90)
      {
        arr1[arr1Index++] = "eighty" + singleD[sIndex++];
        if(sIndex > 8 && index < 8)
        {
          sIndex = 0;
          index++;
        }
        continue;
      }

      arr1[arr1Index++] = tens[index] + singleD[sIndex++];
      if(sIndex > 8 && index < 8)
      {
        sIndex = 0;
        index++;
      } 	  
    }

    String[] arr2 = new String[901];
    arr2[900] = "onethousand";
    int arr2Index = 0;

    //PRINT OUT NUMBER 100 - 999
    for(int y = 100, index2 = 0, index3 = 0; y < 1000; y++)
    {
      if(y % 100 == 0)
      {
        arr2[arr2Index++] = singleD[y/100 - 1] + hundred;
        continue;
      }

      arr2[arr2Index++] = singleD[index2] + hundred + and + arr1[index3++];
      if(index3 > 98)
      {
        index3 = 0;
        index2++;
      }	  
    }

    int sum = 0;

    for(int k = 0; k < arr1.length; k++)
    {
      sum += arr1[k].length();
    }
    for(int o = 0; o < arr2.length; o++)
    {
      sum += arr2[o].length();
    }
    System.out.println("The total number of characters: " + sum);
  }
}