Leetcode: 233. Number of Digit One
First idea consists on counting the number of 1's in all possible inputs and answer the queries in \(O(1)\). As \(0 \leq p \leq 10^9\), we would need \(10^9 \times 32\) bits or \(120\) megabytes just to store the count and the algorithm would have time complexity of \(O(9n) = O(9 \times 10^9)\) what is too slow.
Let's explore the fact that any given input will be a number with at most 9 digits. Be \(c(p)\) the total number of digit 1 appearing in all non-negative integers less than or equal to \(n\). Take \(n=12345\) as example. It has 5 digits. What do we know about numbers with less than 5 digits? Be \(d(p)\) the total number of digit 1 appearing in all non-negative integers with exactly \(p\) digits. If the first digit (left-most digit) is 1, then there are 10 values (0-9) for each of the other digits. If the first digit is not 1, then there are \(\tbinom{p}{q}\) ways to have \(q\) 1-digits in the integer and \(9^{p-q}\) values for the remainder \((p-q)\) digits. So, \(d(p)=10^{p-1}+\sum_{1\leq q \leq p}\tbinom{p}{q} \times 9^{p-q}\).