Find count of multiples of 3 or 5 in given range in C++

In this tutorial, we are going to learn the basic and efficient code of the given problem that is Find count of multiples of 3 or 5 in the given range in C++. Initially, we will know what we have to find.  let the range is 1………n and we have to find the count of those number which is either divisible by either 3 or 5.

eg: given range is 1-20 i.e. { 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,20} , so all the numbers, divisible by 3 or 5 are    {3,5,6,9,10,12,15,18,20 }  count =9.

Here I’m going to explain two methods to solve this problem.

Method1 to count the multiples of 3 or 5 in C++

Use a loop which iterates from 1 – n with the help of condition find it is divisible by 3 or 5  and count all the numbers.

#include<iostream>
using namespace std;
int main()
{
int range,i,count;
cin>>range;
count=0;
for(i=1;i<=range;i++)
{
if(i%3==0||i%5==0)
count++;
}
cout<<count<<endl;
return 0;
}

Input:

20

Output:

9

Time complexity:  O(n) 

This method works perfectly when the range is less than 10^9  if the range is large than 10^9 this method will give TLE (time limit exceed).

An alternative method to count the numbers, divisible by 3 or 5 in C++

We know the count of the number which is divisible by 3 in the given range is equal to the floor(n/3). In the range 1-20 count number divisible by 3 are floor(20/3) = 6   i.e. { 3,6,9,12,15,18}.

Similarly, the count of the number which is divisible by 5 in the given range is equal to the floor(n/5). In the range 1-20 count number divisible by 5 are floor (20/5)=4  i.e.{ 5,10,15,20}.

And count of the number which is divisible by 3 and 5 in the given range is equal to the floor(n/3)+floor(n/5)-floor(n/15). In the range 1-20 count number divisible by 3 are floor(20/3)+floor(20/5) – floor(n/15) =6+4-1=9 i.e. { 3,5,6,9,10,12,15,15,18,20} – {15} = { 3,5,6,9,10,12,15,18,20}.

#include<iostream>
using namespace std;
int main()
{
long long int r,i,count;
cin>>r;
count=r/3;
count+=r/5;
count-=r/15;
cout<<count<<endl;
return 0;
}

Input:

100

Output:

47

Time complexity:  O(1)

This method works perfectly when the range is either less than 10^9  or more than 10^9.

Read other tutorials as well,

• How to find the nth prime number in Java

2 responses to “Find count of multiples of 3 or 5 in given range in C++”

1. Divyesh Srivastava says:

   June 3, 2019 at 9:57 am

   Nice post on basis of time complexity .

   Reply
2. Rohit Nandan Dubey says:

   June 3, 2019 at 1:36 pm

   Thanks 🙂

   Reply