Count of Multiples of A ,B or C less than or equal to N

0 0 5 minutes read

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 b
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 c
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 code
int main()
{
    long a = 7, b = 3, c = 5, n = 100;
 
    cout << divTermCount(a, b, c, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
     
class GFG
{
     
// Function to return the
// gcd of a and b
static 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 c
static 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 code
static 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 approach
using System;
     
class GFG
{
     
// Function to return the
// gcd of a and b
static 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 c
static 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 code
static 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 b
function 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 c
function 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 code
n = 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:

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 zambiatek!