Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8 Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem?
I was thinking of constructing all possible numbers that fit into the integer size of the language that I am using, through a recursive procedure, but I am not sure how to do that. It seems complicated. Is there an alternative solution apart from taking some of the digits from the given set and constructing numbers?
This is much easier than inclusion&ndash;exclusion.  Compute the number of natural numbers smaller than $N$ that contain none of the digits 2, 4, 6, 8 and subtract that from $N$ (or $N+1$ if you're including zero).  To compute the number of naturals that contain none of 2, 4, 6, 8, observe that, if $M\leq N$ (padded with zeroes so $M$ also has $d$ digits) then $M$ and $N$ must agree on their first $i$ digits (for some $0\leq i\leq d$), then the $(i+1)$st digit of $M$ must be less than the $(i+1)$st digit of $N$ and the $(i+2)$nd, ..., $d$th digits of $M$ can be any of 0, 1, 3, 5, 7, 9.