Problem:
Find the number of non-divisible numbers in a range starting from 1 to N, for a given set.
Problem Link [Courtesy: geeksforgeeks.org]
Appeared as interview question in Paytm.
Solution:
The given set is {2,3,4,5,6,7,8,9,10}. The set can be minimized to {2,3,5,7} as these are the prime numbers and rest of the numbers of the set can be formed using these numbers.
Now we can use SET UNION formula to solve the problem.
We need to subtract all the even numbers, this can be done by subtracting n/2 from n.
Need to subtract all the numbers multiple of 3, this can be done by subtracting n/3 from n. But in n/3 numbers some are multiple of 2, like 6,12 those are already deducted from n. So minimize that we need to add n/6.
Same goes for 5 and 7.
Here if we consider to remove the multiple for 2,3,5 and 7 and not overlapping than we can think of the scenario as each multiple a SET those have some common portions. So we can apply set union formula :
n(AUBUCUD) = n(A)+n(B)+n(C)+n(D) – n(A∩B) – n(A∩C) – n(A∩D) – n(C∩B) – n(D∩B) – n(C∩D) + n(A∩B∩C) + n(B∩C∩D) + n(A∩B∩D) + n(A∩B∩D)
– n(A∩B∩C∩D).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> #include <iostream> using namespace std; int main() { long long int n,excluding_numbers; int t; long long int remaining_numbers=1; scanf("%d",&t); while(t--) { scanf("%lld",&n); //SET UNION(2,3,5,7) excluding_numbers = n/2+ n/3 +n/5 + n/7 - n/6 - n/10 - n/14 - n/15 -n/21 -n/35 + n/30 + n/105 + n/70 +n/42 - n/210; //remaining_numbers+= (n-n/2) + (n-(n/3-n/6)) + (n-(n/5-n/10-n/15)) + (n-(n/7-n/14-n/21-n/35)); remaining_numbers = n - excluding_numbers; cout<<remaining_numbers<<endl; } return 0; } |