Count Digit One

Problem Statement

Count Digit One Take every positive whole number from 1 up to and including N , write each one out in the ordinary decimal way, and count how many times the character 1 appears across all of them. A number may of course contribute more than once: 11 contributes two. Report that total. Input Format A single line containing one integer N . Output Format Print a single integer -- how many times the digit 1 occurs in the decimal spellings of 1, 2, ..., N . Constraints 0 <= N <= 100000000 When N is 0 the list of numbers is empty, so the answer is 0 . Examples Example 1 Input: 13 Output: 6 Explanation: the numbers are 1, 2, ..., 13 . A 1 appears once in 1 , once in 10 , twice in 11 , once in 12 and once in 13 , which is 6 occurrences in total. Example 2 Input: 100 Output: 21 Explanation: 1 appears once as a units digit in each of 1, 11, 21, ..., 91 (ten times), once as a tens digit in each of 10, 11, ..., 19 (ten more), and once as the leading digit of 100 . Example 3 Input: 0 Output: