Given four integers N, A, B and C. The task is to find the count of integers from the range [1, N] which are divisible by either A, B or C.
Examples:
Input: A = 2, B = 3, C = 5, N = 10
Output: 8
2, 3, 4, 5, 6, 8, 9 and 10 are the only number from the
range [1, 10] which are divisible by either 2, 3 or 5.Input: A = 7, B = 3, C = 5, N = 100
Output: 55
Approach: An efficient approach is to use the concept of set theory. As we have to find numbers that are divisible by a or b or c.
- Let n(a): count of numbers divisible by a.
- Let n(b): count of numbers divisible by b.
- Let n(c): count of numbers divisible by c.
- n(a ? b): count of numbers divisible by a and b.
- n(a ? c): count of numbers divisible by a and c.
- n(b ? c): count of numbers divisible by b and c.
- n(a ? b ? c): count of numbers divisible by a and b and c.
According to set theory,
n(a ? b ? c) = n(a) + n(b) + n(c) – n(a ? b) – n(b ? c) – n(a ? c) + n(a ? b ? c)
So. the count of numbers divisible either by A, B or C is (num/A) + (num/B) + (num/C) – (num/lcm(A, B)) – (num/lcm(A, B)) – (num/lcm(A, C)) + – (num/lcm(A, B, C))
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the// gcd of a and blong gcd(long a, long b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return the count of integers// from the range [1, num] which are// divisible by either a, b or clong divTermCount(long a, long b, long c, long num){ // Calculate the number of terms divisible by a, b // and c then remove the terms which are divisible // by both (a, b) or (b, c) or (c, a) and then // add the numbers which are divisible by a, b and c return ((num / a) + (num / b) + (num / c) - (num / ((a * b) / gcd(a, b))) - (num / ((c * b) / gcd(c, b))) - (num / ((a * c) / gcd(a, c))) + (num / ((a * b * c) / gcd(gcd(a, b), c))));}// Driver codeint main(){ long a = 7, b = 3, c = 5, n = 100; cout << divTermCount(a, b, c, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*; class GFG{ // Function to return the// gcd of a and bstatic long gcd(long a, long b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return the count of integers// from the range [1, num] which are// divisible by either a, b or cstatic long divTermCount(long a, long b, long c, long num){ // Calculate the number of terms divisible by a, b // and c then remove the terms which are divisible // by both (a, b) or (b, c) or (c, a) and then // add the numbers which are divisible by a, b and c return ((num / a) + (num / b) + (num / c) - (num / ((a * b) / gcd(a, b))) - (num / ((c * b) / gcd(c, b))) - (num / ((a * c) / gcd(a, c))) + (num / ((a * b * c) / gcd(gcd(a, b), c))));}// Driver codestatic public void main (String []arr){ long a = 7, b = 3, c = 5, n = 100; System.out.println(divTermCount(a, b, c, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the # gcd of a and b def gcd(a, b) : if (a == 0) : return b; return gcd(b % a, a); def lcm (x, y): return (x * y) // gcd (x, y)# Function to return the count of integers # from the range [1, num] which are # divisible by either a, b or c def divTermCount(a, b, c, num) : # Calculate the number of terms divisible by a, b # and c then remove the terms which are divisible # by both (a, b) or (b, c) or (c, a) and then # add the numbers which are divisible by a, b and c return (num // a + num // b + num // c - num // lcm(a, b) - num // lcm(c, b) - num // lcm(a, c) + num // (lcm(lcm(a, b), c))) # Driver code if __name__ == "__main__" : a = 7; b = 3; c = 5; n = 100; print(divTermCount(a, b, c, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation for above approachusing System; class GFG{ // Function to return the// gcd of a and bstatic long gcd(long a, long b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return the count of integers// from the range [1, num] which are// divisible by either a, b or cstatic long divTermCount(long a, long b, long c, long num){ // Calculate the number of terms divisible by a, b // and c then remove the terms which are divisible // by both (a, b) or (b, c) or (c, a) and then // add the numbers which are divisible by a, b and c return ((num / a) + (num / b) + (num / c) - (num / ((a * b) / gcd(a, b))) - (num / ((c * b) / gcd(c, b))) - (num / ((a * c) / gcd(a, c))) + (num / ((a * b * c) / gcd(gcd(a, b), c))));}// Driver codestatic public void Main (String []arr){ long a = 7, b = 3, c = 5, n = 100; Console.WriteLine(divTermCount(a, b, c, n));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach // Function to return the// gcd of a and bfunction gcd(a, b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return the count of integers// from the range [1, num] which are// divisible by either a, b or cfunction divTermCount(a, b, c, num){ // Calculate the number of terms divisible by a, b // and c then remove the terms which are divisible // by both (a, b) or (b, c) or (c, a) and then // add the numbers which are divisible by a, b and c return Math.ceil(((num / a) + (num / b) + (num / c) - (num / ((a * b) / gcd(a, b))) - (num / ((c * b) / gcd(c, b))) - (num / ((a * c) / gcd(a, c))) + (num / ((a * b * c) / gcd(gcd(a, b), c)))));}// Driver coden = 13;var a = 7, b = 3, c = 5, n = 100;document.write(divTermCount(a, b, c, n));// This code is contributed by SoumikMondal</script> |
Output:
55
Time Complexity: O(log(min(a, b))), where a and b are the parameters of gcd
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
