Number of even numbers having digit 2 in them. I am trying to count numbers from 1 to N which exist in  A121022 but I am unable to think of solving in better than O(NLog(N)) , can you suggest a better algorithm? 
 A: For a convenient number $N = 10^k-1$ the question can be done much more easily.

How many even numbers from $1$ to $10^k-1$ have at least one 2 present in its digits?

We count instead how many numbers don't have a two.
Approach via multiplication principle.  Pick the first digit: It can be any of $\{0,1,3,4,\dots,9\}$.  Similarly for the second digit, etc... on up until the ones digit where it can be any of $\{0,4,6,8\}$
There are then $4\cdot 9^{k-1}$ even numbers without a two including the number zero.  This is out of $5\cdot 10^{k-1}$ even numbers from $0$ to $10^k-1$ including zero.
Thus there are $5\cdot 10^{k-1}-4\cdot 9^{k-1}$ even numbers with at least one two in the range $1$ to $10^k-1$
A: Let $A(N)$ be what you're trying to find.
Let $A_i(N)$ be the number of integers $0 \le x \le N$ containing a $2$ whose units digit is $i$. Thus $A(N) = A_0(N) + A_2(N) + A_4(N) + A_6(N) + A_8(N)$, and
$A_2(N) = 1 + \lfloor (N-2)/10 \rfloor $ if $N \ge 2$.
For $i \ne 2$, 
$$A_i(N) = \sum_{j=0}^9 A_j(\lfloor((N-i)/10\rfloor)$$
This should let you compute it in $O(\log(N))$.
