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,
Nice post on basis of time complexity .
Thanks 🙂