2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Are you looking for an algorithm or a formula? $\endgroup$ – Raphael Aug 16 '14 at 18:30
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.