I read about a programming puzzle today on programming.reddit. Here’s the problem:
“If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?”
To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, ‘and’, and punctuation), and sorted alphabetically so that the first six integers are
and the last is
then reading top to bottom, left to right, the 28th letter completes the spelling of the integer “eighteenmillion”.
The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?
 For example, 911,610,034 is written “ninehundredelevenmillionsixhundredtenthousandthirtyfour”; 500,000,000 is written “fivehundredmillion”; 1,709 is written “onethousandsevenhundrednine”.
I’ve thought about this, and I can’t think of an efficient way to solve this. In a world of infinite memory and processor power you would:
- Generate the numbers from 1 to 999,999,999
- Apply a number_to_words() function on every number and into a mapping of the form ([number], [number in english])
- Sort the list on the numbers in english
- Count characters and sum numbers until character 51,000,000,000 is reached
The problem is that this would take WAY too long and WAY too much memory. I initially thought that a lazy data structure would work, but since you need to sort the list, you need to have all the elements, so you’re kinda screwed anyhow. I made a quick test where I wrote the numbers to a file to save on memory, but I was up to 1.5 GB by the time (± 10 minutes) I reached twentymillion; needless to say I stopped the process right there.
Does anyone have a brilliant idea how this could be solved? Maybe by generating the numbers starting with 8 first, then by 5, then 4, etc.?