I am reading the problem:
How many numbers between $[1, 100]$ are multiples of $2$ or multiples of $3$? (Caution to avoid double counting)
My approach:
Numbers that are multiple of $2$
$2, 4, 6, 8, ....100$
$1, 2, 3, 4, ....\frac{100}{2}=50$
Hence $50$ multiples of $2$
Numbers that are multiple of $3$
$3, 6, 9, 12, ....99$
$1, 2, 3, 4, ....\frac{99}{3}=33$
Hence $33$ multiples of $3$. But these double count the multiples of $2$ when the number is a multiple of $6$.
Numbers that are multiple of $6$:
$6, 12, 18, 24, ....96$
$1, 2, 3, 4, ....\frac{96}{6}=16$
So the answer to the original question is:
$50 + 33 - 16 = 67$
Is there something in the logic that could be improved or be more efficient? Am I over complicating something?
$\endgroup$ 31 Answer
$\begingroup$No, your logic is perfect in this case. The only way I can think of to perhaps make it a little more refined is this: to count the number of multiples of $2$, or $3$ or $6$, you can observe that the sequences form arithmetic progressions, whose $n^{th}$ term is given by:$$a_n=a_1+(n-1)d$$So, for example, number of multiples of $6$ would be:$$96=6+(n-1)6$$So $n=16$, hence $16$ multiples of $6$.
Perhaps this could shave off a few seconds from your solution, for intervals more complex than $[1,100]$, such as, say, $[23,567]$, in which case you wouldn't get a simple ratio between the term and the order of the term.
$\endgroup$ 1
