Number letter counts
Problem 17
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?
(https://projecteuler.net/problem=17)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.
Personally, Problem 17 was really fun.
It doesn't involve numerical analysis specifically, yet it requires a clever algorithm to solve.
English has a lot of irregular expressions, and number is one. (11 is not ten-one, it is eleven.)
Having many Chinese friends, I found that Chinese has really formalized number expression which doesn't have any exceptions. In China, people count 12 as ten-two, and 21 as two-ten-one.
Anyway, because English has its own unique way of expressing numbers into its language, we will need several steps in our algorithms to solve this problem.
We need three main sets of English words:
private static final String[] UNIT = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; private static final String[] TENTH = {"twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"}; private static final String[] TEN = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
And three main keywords:
private static final String THOUSAND = "thousand"; private static final String HUNDRED = "hundred"; private static final String AND = "and";
My algorithm was starting with unit digit numbers and gradually increasing the level to two-digit and three-digit numbers.
First, get the sum of unit digit numbers from "one" to "nine":
// 1 to 9 int unitSum = 0; for (String n : UNIT) unitSum += n.length();
Once we get this sum, we will reuse it A LOT as "one" to "nine" appears every ten times in counting.
Second, get the sum of the numbers from "one" to "ninety nine" (without space):
// 1 to 99 int twoDigit = unitSum*9; for (String n : TEN) twoDigit += n.length(); for (String n : TENTH) twoDigit += n.length()*10;
Notice that unitSum was added 9 times, TENTH was added once, and TEN was added 10 times.
("one" to "nine" appears in 1~9, skips 11~19, appears in 21~29, 31~39, ... 91~99)
(For the skipped 11~19, we add each element of TENTH)
(From 21~99, we only added unit digits so far, so we will add each element of TEN 10 times. For example, "twenty" appears 10 times from 20 ~ 29)
Third, we will get the sum from "one" to "Nine Hundred And Ninety Nine":
// 1 to 999 int threeDigit = 0;
threeTemp is 1~99 right now.
int threeTemp = twoDigit;
Then we are going to add "Hundred and" to each number from 1~99.
So it's going to be "Hundred and one," "Hundred and two," "Hundred and ninety nine,"...
without the beginning numbers. (So it's not a complete number like "One Hundred and One.")
threeTemp += (HUNDRED.length() + AND.length())*99; threeTemp += HUNDRED.length();
Lastly, we are going to add those beginning numbers to complete the 3-digit numbers.
for (String u : UNIT) threeDigit += u.length()*100 + threeTemp;
So by now, our variable threeDigit has all the letter countings from 100~999.
The only thing we need to do is to add 1~99 counting to threeDigit complete 1~999 counting.
threeDigit += twoDigit; // 1 to 99 (without any hundredth digit)
Because the question asked for 1~1000, we are going to add the "One Thousand" to the sum.
// 1000 int fourDigit = UNIT[0].length() + THOUSAND.length(); // one thousand System.out.println(fourDigit + threeDigit);
Answer is 21124
Execution time is 2.075885 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem017.java
