Interview question.

general
1

I recently came across this question.
You are given 4 integers n,a,b,c. You have to find out how many integers between [1,n] are divisible by a,b,c.
I tried using the formula of n(a U b U c) but got a wrong answer. Can someone help me with this one? (Unfortunately I do not have a link for the question as this was an interview question)
Thank you.

2

we know that n(a U b U c)=n(a)+n(b)+n©-n(a ∩ b)-n(a ∩ c)-n(b ∩ c)+n(a ∩ b ∩ c)

so final answer will be (n/a)+(n/b)+(n/c)-(n/(LCM(a,b))-(n/(LCM(a,c))-(n/(LCM(b,c))+(n/(LCM(a,b,c)).

3 Likes
3

@chari407 although utkarsh has explained it. Consider 4 and 6. So you have to eliminate the numbers which can be divided by both 4 and 6 if you multiply them you will escape 12 and start from 24 so you have not removed 12 which was supposed to be because it was divisible by 4 and 6 both.

3 Likes
4

You can search for Inclusion-Exclusion Principle to know more about the way of solving this problem.

5

Hey thanks for the answer. I actually used this.
(n/a)+(n/b)+(n/c)-(n/((ab))-(n/((ac))-(n/((bc))+(n/((ab*c)).
Can you please explain why that LCM in the denominator?

6

because LCM is the smallest number that is divisible by all those numbers.

7

Can you give a more detailed explanation? I actually dont even know why did the union formula is used ehre, meaning i have literally no idea at this moment. I wll appreciate some explanation ^^

8

@vijju123 union formula is used because we want to find the numbers divisible by a or b or c and hence the formula used. I have explained it with an example too why it has to be LCM. In case of any doubt feel free to ask:)

9

Oh i get it now! I misunderstood it as "How many numbers in [1,n] are divisible by a AND b AND c (simultaneously). " and so i thought it should just be N/LCM(a,b,c) and where did union come from XD.

1 Like
10

Q:why LCM is denominator?
ans:we have to find the multiples of both a,b.LCM means “Least Common Multiple” so LCM(a,b) is the smallest number that is multiple of both a,b.
Now multiples of both a,b=multiples of LCM(a,b).

try to understand,i am not good at explanation.

11

Thank you bro.Got it.

12

Thanks a lot guys.