Problem
A sign maker spells out house numbers in words and pays by the letter. Write every number from 1 to n in American English, without the word "and": 342 is "three hundred forty-two" and 2005 is "two thousand five". Spaces and hyphens are free; only letters count.
Implement number_letter_counts(n).
Spellings: one to nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand. Numbers from 1,000 up are written as the thousands part (itself in words, up to ninety-nine) followed by "thousand" and then the rest, if any.
Input
n: The last number to write.
Output
Return the total number of letters used for 1, 2, ..., n. For n = 0 nothing is written and the answer is 0.
Constraints
0 ≤ n ≤ 99,999
Examples
Input:
n = 3
Expected output:
expected = 11
Input:
long long n = 3;
Expected output:
long long expected = 11;
Input:
long n = 3;
Expected output:
long expected = 11;
Explanation
"one", "two" and "three" have 3 + 3 + 5 = 11 letters.
Input:
n = 21
Expected output:
expected = 121
Input:
long long n = 21;
Expected output:
long long expected = 121;
Input:
long n = 21;
Expected output:
long expected = 121;
Explanation
1 to 19 use 106 letters, twenty adds 6 and twenty-one adds 9, for 121.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Handle 1 to 19 with a table, then the tens words for 20 to 90.
Hint 2
A three-digit block is the hundreds word plus "hundred" plus the last two digits.
Hint 3
For numbers of 1,000 and up, spell the thousands block, add "thousand", then spell the rest.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.