# 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?

• Are you looking for an algorithm or a formula? – Raphael Aug 16 '14 at 18:30

This is much easier than inclusion–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.
This is really a math question. The idea is to use the inclusion-exclusion principle. For every given position, it is possible (with some effort) to count the number of integers at most $n$ which contain one of 2,4,6,8 in that position. With more effort, you can do this for several positions at once. Now you can use the inclusion-exclusion formula to determine the quantity you are after.