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