Robert Eisele
Engineer, Systems Architect and DBA

# Project Euler 17: 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?

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.

## Solution

Numbers between 0 and 12 have unique names, from 13 to 19 the names have a teen-suffix and numbers between 20 and 99 are constructed by prefixing a tenth-prefix, except for zero, there is no twenty-zero, but of course a twenty-one and twenty-two. These ten-prefixes get suffixes between one and nine. This information can already be coded:

// proper nouns
var proper = [
0,
"one".length,
"two".length,
"three".length,
"four".length,
"five".length,
"six".length,
"seven".length,
"eight".length,
"nine".length,
"ten".length,
"eleven".length,
"twelve".length,
"thirteen".length,
"fourteen".length,
"fifteen".length,
"sixteen".length,
"seventeen".length,
"eighteen".length,
"nineteen".length
];

// tenth prefixes
var tenth = [
"twenty".length,
"thirty".length,
"forty".length,
"fifty".length,
"sixty".length,
"seventy".length,
"eighty".length,
"ninety".length
];

// Returns the length of the numbers between 0 and 99
function below100(n) {

if (n < 20)
return proper[n];

return tenth[n / 10 - 2 | 0] + proper[n % 10];
}

So far so good. We can now calculate the length of the numbers between 0 and 99. After that, every number below 1000 gets a hundred suffix, like 234 is two-hundred plus the same as a number below 100. The question reminds us, that the tenths are added with an "and", like two-hundred and thirty-four, but only if it's not exactly a hundreds, like three-hundred. If a number is greater than 999, it's only necessary to append the thousandth part. Implemented, this can look like:

function numberLength(n) {

if (n < 100)
return below100(n);

var res = 0;
var h = Math.floor(n / 100) % 10;
var t = Math.floor(n / 1000);
var s = n % 100;

if (n > 999)
res+= below100(t) + "thousand".length;
if (h !== 0)
res+= proper[h] + "hundred".length;
if (s !== 0)
res+= "and".length + below100(s);
return res;
}

Thats cool we have a $$O(1)$$ solution to calculate the length of a number name, which can now be used to loop over 1000 times to come up with the final solution:

function solution(n) {

var num = 0;
for (var i = 1; i <= n; i++) {
num+= numberLength(i);
}
return num;
}
solution(1000);

« Back to problem overview