Given an integerĀ 
. The task is to count all such numbers that are less than or equal to N which are divisible by any of 2 or 3 or 5.
Note: If a number less than N is divisible by both 2 or 3, or 3 or 5, or all of 2,3 and 5 then also it should be counted only once.
Examples:Ā
Ā
Input : N = 5 Output : 4 Input : N = 10 Output : 8
Ā
Simple Approach: A simple approach is to traverse from 1 to N and count multiple of 2, 3, 5 which are less than equal to N. To do this, iterate up to N and just check whether a number is divisible by 2 or 3 or 5. If it is divisible, increment the counter and after reaching N, print the result.
Time Complexity: O(N).
Efficient Approach: An efficient approach is to use the concept of set theory. As we have to find numbers that are divisible by 2 or 3 or 5.
Ā
Now the task is to find n(a),n(b),n(c),n(a
b), n(bc), n(ac), and n(abc). All these terms can be calculated using Bit masking. In this problem we have taken three numbers 2,3, and 5. So, the bit mask should be of 2^3 bits i.e 8 to generate all combination of 2,3, and 5.
Now according to the formula of set union, all terms containing odd numbers of (2,3,5) will add into the result and terms containing even number of (2,3,5) will get subtracted.
Below is the implementation of the above approach:Ā
Ā
C++
// CPP program to count number of multiples // of 2 or 3 or 5 less than or equal to NĀ
#include <bits/stdc++.h>Ā
using namespace std;Ā
// Function to count number of multiples // of 2 or 3 or 5 less than or equal to Nint countMultiples(int n){Ā Ā Ā Ā // As we have to check divisibilityĀ Ā Ā Ā // by three numbers, So we can implementĀ Ā Ā Ā // bit maskingĀ Ā Ā Ā int multiple[] = { 2, 3, 5 };Ā Ā Ā Ā Ā Ā Ā Ā Ā int count = 0, mask = pow(2, 3);Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i < mask; i++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // we check whether jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set or not, if jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set, simply multiplyĀ Ā Ā Ā Ā Ā Ā Ā // to prodĀ Ā Ā Ā Ā Ā Ā Ā int prod = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j < 3; j++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check for set bitĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (i & 1 << j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prod = prod * multiple[j];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (__builtin_popcount(i) % 2 == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count + n / prod;Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count - n / prod;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā return count;}Ā
// Driver codeint main(){Ā Ā Ā Ā int n = 10;Ā Ā Ā Ā Ā Ā Ā Ā Ā cout << countMultiples(n) << endl;Ā Ā Ā Ā Ā Ā Ā Ā Ā return 0;} |
Java
// Java program to count number of multiples // of 2 or 3 or 5 less than or equal to NĀ
class GFG{static int count_setbits(int N){ Ā Ā Ā Ā int cnt=0;Ā Ā Ā Ā while(N>0)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā cnt+=(N&1);Ā Ā Ā Ā Ā Ā Ā Ā N=N>>1;Ā Ā Ā Ā }Ā Ā Ā Ā return cnt;}Ā
// Function to count number of multiples // of 2 or 3 or 5 less than or equal to Nstatic int countMultiples(int n){Ā Ā Ā Ā // As we have to check divisibilityĀ Ā Ā Ā // by three numbers, So we can implementĀ Ā Ā Ā // bit maskingĀ Ā Ā Ā int multiple[] = { 2, 3, 5 };Ā Ā Ā Ā Ā Ā Ā Ā Ā int count = 0, mask = (int)Math.pow(2, 3);Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i < mask; i++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // we check whether jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set or not, if jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set, simply multiplyĀ Ā Ā Ā Ā Ā Ā Ā // to prodĀ Ā Ā Ā Ā Ā Ā Ā int prod = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j < 3; j++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check for set bitĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if ((i & 1 << j)>0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prod = prod * multiple[j];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (count_setbits(i) % 2 == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count + n / prod;Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count - n / prod;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā return count;}Ā
// Driver codepublic static void main(String[] args){Ā Ā Ā Ā int n = 10;Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println(countMultiples(n));}}// this code is contributed by mits |
Python 3
# Python3 program to count number of multiples # of 2 or 3 or 5 less than or equal to N Ā
Ā
# Function to count number of multiples # of 2 or 3 or 5 less than or equal to N def countMultiples( n): Ā
Ā Ā Ā Ā # As we have to check divisibility Ā Ā Ā Ā # by three numbers, So we can implement Ā Ā Ā Ā # bit masking Ā Ā Ā Ā multiple = [ 2, 3, 5 ] Ā Ā Ā Ā Ā Ā Ā Ā Ā count = 0Ā Ā Ā Ā mask = int(pow(2, 3)) Ā Ā Ā Ā for i in range(1,mask): Ā Ā Ā Ā Ā Ā Ā Ā # we check whether jth bit Ā Ā Ā Ā Ā Ā Ā Ā # is set or not, if jth bit Ā Ā Ā Ā Ā Ā Ā Ā # is set, simply multiply Ā Ā Ā Ā Ā Ā Ā Ā # to prod Ā Ā Ā Ā Ā Ā Ā Ā prod = 1Ā Ā Ā Ā Ā Ā Ā Ā for j in range(3): Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # check for set bit Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (i & (1 << j)): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prod = prod * multiple[j] Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (bin(i).count('1') % 2 == 1): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count + n // prod Ā Ā Ā Ā Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count - n // prod Ā Ā Ā Ā Ā Ā Ā Ā Ā return count Ā
Ā
# Driver codeif __name__=='__main__':Ā Ā Ā Ā n = 10Ā Ā Ā Ā print(countMultiples(n)) Ā Ā Ā Ā Ā # This code is contributed by ash264 |
C#
// C#Ā program to count number of multiples // of 2 or 3 or 5 less than or equal to N Ā
Ā
using System;Ā
public class GFG{Ā Ā Ā Ā static int count_setbits(int N) { Ā Ā Ā Ā int cnt=0; Ā Ā Ā Ā while(N>0) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā cnt+=(N&1); Ā Ā Ā Ā Ā Ā Ā Ā N=N>>1; Ā Ā Ā Ā } Ā Ā Ā Ā return cnt; } Ā
// Function to count number of multiples // of 2 or 3 or 5 less than or equal to N static int countMultiples(int n) { Ā Ā Ā Ā // As we have to check divisibility Ā Ā Ā Ā // by three numbers, So we can implement Ā Ā Ā Ā // bit masking Ā Ā Ā Ā int []multiple = { 2, 3, 5 }; Ā Ā Ā Ā Ā Ā Ā Ā Ā int count = 0, mask = (int)Math.Pow(2, 3); Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i < mask; i++) { Ā
Ā Ā Ā Ā Ā Ā Ā Ā // we check whether jth bit Ā Ā Ā Ā Ā Ā Ā Ā // is set or not, if jth bit Ā Ā Ā Ā Ā Ā Ā Ā // is set, simply multiply Ā Ā Ā Ā Ā Ā Ā Ā // to prod Ā Ā Ā Ā Ā Ā Ā Ā int prod = 1; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j < 3; j++) { Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check for set bit Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if ((i & 1 << j)>0) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prod = prod * multiple[j]; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (count_setbits(i) % 2 == 1) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count + n / prod; Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count - n / prod; Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā return count; } Ā
// Driver code Ā Ā Ā Ā static public void Main (){Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int n = 10; Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine(countMultiples(n)); } } //This code is contributed by ajit. |
PHP
<?php// PHP program to count number // of multiples of 2 or 3 or 5 // less than or equal to NĀ
// Bit count functionfunction popcount($value){Ā Ā Ā Ā $count = 0;Ā Ā Ā Ā while($value)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā $count += ($value & 1);Ā Ā Ā Ā Ā Ā Ā Ā $value = $value >> 1;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā return $count;}Ā
// Function to count number ofĀ // multiples of 2 or 3 or 5 less// than or equal to Nfunction countMultiples($n){Ā Ā Ā Ā // As we have to check divisibilityĀ Ā Ā Ā // by three numbers, So we can Ā Ā Ā Ā // implement bit maskingĀ Ā Ā Ā $multiple = array(2, 3, 5);Ā Ā Ā Ā Ā Ā Ā Ā Ā $count = 0;Ā Ā Ā Ā $mask = pow(2, 3);Ā Ā Ā Ā Ā Ā Ā Ā Ā for ($i = 1; $i < $mask; $i++)Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // we check whether jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set or not, if jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set, simply multiplyĀ Ā Ā Ā Ā Ā Ā Ā // to prodĀ Ā Ā Ā Ā Ā Ā Ā $prod = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for ($j = 0; $j < 3; $j++) Ā Ā Ā Ā Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check for set bitĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if ($i & 1 << $j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $prod = $prod * $multiple[$j];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (popcount($i) % 2 == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $count = $count + (int)($n / $prod);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $count = $count - (int)($n / $prod);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā return $count;}Ā
// Driver code$n = 10;Ā Ā Ā Ā Ā echo countMultiples($n);Ā Ā Ā Ā Ā // This code is contributed by ash264?> |
Javascript
<script>Ā
// javascript program to count number of multiples // of 2 or 3 or 5 less than or equal to Nfunction count_setbits(N){ Ā Ā Ā Ā var cnt=0;Ā Ā Ā Ā while(N>0)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā cnt+=(N&1);Ā Ā Ā Ā Ā Ā Ā Ā N=N>>1;Ā Ā Ā Ā }Ā Ā Ā Ā return cnt;}Ā
// Function to count number of multiples // of 2 or 3 or 5 less than or equal to Nfunction countMultiples(n){Ā Ā Ā Ā // As we have to check divisibilityĀ Ā Ā Ā // by three numbers, So we can implementĀ Ā Ā Ā // bit maskingĀ Ā Ā Ā var multiple = [ 2, 3, 5 ];Ā Ā Ā Ā Ā Ā Ā Ā Ā var count = 0, mask = parseInt(Math.pow(2, 3));Ā Ā Ā Ā Ā Ā Ā Ā Ā for (i = 1; i < mask; i++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // we check whether jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set or not, if jth bitĀ Ā Ā Ā Ā Ā Ā Ā // is set, simply multiplyĀ Ā Ā Ā Ā Ā Ā Ā // to prodĀ Ā Ā Ā Ā Ā Ā Ā var prod = 1;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (j = 0; j < 3; j++) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check for set bitĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if ((i & 1 << j)>0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā prod = prod * multiple[j];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // check multiple of product Ā Ā Ā Ā Ā Ā Ā Ā if (count_setbits(i) % 2 == 1)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count + parseInt(n / prod);Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count = count - parseInt(n / prod);Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā return count;}Ā
// Driver codevar n = 10;Ā
document.write(countMultiples(n));Ā
// This code is contributed by 29AjayKumar Ā
</script> |
Output:Ā
8
Ā
Time Complexity: O(1)
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!
