Count the numbers divisible by 'M' in a given range
Last Updated :
20 Dec, 2022
A and B are two numbers which define a range, where A <= B. Find the total numbers in the given range [A ... B] divisible by 'M'
Examples:
Input : A = 25, B = 100, M = 30
Output : 3
Explanation : In the given range [25 - 100],
30, 60 and 90 are divisible by 30
Input : A = 6, B = 15, M = 3
Output : 4
Explanation : In the given range [6 - 15],
6, 9, 12 and 15 are divisible by 3
Method 1 : [Brute-force]
Run a loop from A to B. If a number divisible by 'M' is found, increment counter.
Below is the implementation of above method:
C++
// Program to count the numbers divisible by
// M in a given range
#include <bits/stdc++.h>
using namespace std;
int countDivisibles(int A, int B, int M)
{
// Variable to store the counter
int counter = 0;
// Running a loop from A to B and check
// if a number is divisible by M.
for (int i = A; i <= B; i++)
if (i % M == 0)
counter++;
return counter;
}
// Driver code
int main()
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
cout << countDivisibles(A, B, M) << endl;
return 0;
}
// Java program to count the numbers divisible by
// M in a given range
import java.io.*;
class GFG {
// Function to count the numbers divisible by
// M in a given range
static int countDivisibles(int A, int B, int M)
{
// Variable to store the counter
int counter = 0;
// Running a loop from A to B and check
// if a number is divisible by M.
for (int i = A; i <= B; i++)
if (i % M == 0)
counter++;
return counter;
}
// driver program
public static void main(String[] args)
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
System.out.println(countDivisibles(A, B, M));
}
}
// Contributed by Pramod Kumar
# Program to count the numbers
# divisible by M in a given range
def countDivisibles(A, B, M):
# Variable to store the counter
counter = 0;
# Running a loop from A to B
# and check if a number is
# divisible by M.
for i in range(A, B):
if (i % M == 0):
counter = counter + 1
return counter
# Driver code
# A and B define the range,
# M is the dividend
A = 30
B = 100
M = 30
# Printing the result
print(countDivisibles(A, B, M))
# This code is contributed by Sam007.
// C# program to count the numbers
// divisible by M in a given range
using System;
public class GFG {
// Function to count the numbers divisible by
// M in a given range
static int countDivisibles(int A, int B, int M)
{
// Variable to store the counter
int counter = 0;
// Running a loop from A to B and check
// if a number is divisible by M.
for (int i = A; i <= B; i++)
if (i % M == 0)
counter++;
return counter;
}
// driver program
public static void Main()
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
Console.WriteLine(countDivisibles(A, B, M));
}
}
// This code is contributed by Sam007
<?php
// PHP Program to count the
// numbers divisible by
// M in a given range
function countDivisibles($A, $B, $M)
{
// Variable to store the counter
$counter = 0;
// Running a loop from
// A to B and check
// if a number is
// divisible by M.
for ($i = $A; $i <= $B; $i++)
if ($i % $M == 0)
$counter++;
return $counter;
}
// Driver Code
// A and B define the range,
// M is the dividend
$A = 30;
$B = 100;
$M = 30;
// Printing the result
echo countDivisibles($A, $B, $M), "\n";
// This code is contributed by ajit
?>
<script>
// Javascript Program to count the
// numbers divisible by
// M in a given range
function countDivisibles(A, B, M)
{
// Variable to store the counter
let counter = 0;
// Running a loop from
// A to B and check
// if a number is
// divisible by M.
for (let i = A; i <= B; i++)
if (i % M == 0)
counter++;
return counter;
}
// Driver Code
// A and B define the range,
// M is the dividend
let A = 30;
let B = 100;
let M = 30;
// Printing the result
document.write(countDivisibles(A, B, M));
// This code is contributed by gfgking.
</script>
Output:
3
Time Complexity: O(B)
Auxiliary Space: O(1)
Method 2 : [Better]
The loop can be modified by incrementing the iterator 'M' times after the first divisible is found. Also, if 'A' is less than 'M', it can be changed to 'M', because a number less than 'M' can not be divided by it.
Method 3 : [Efficient]
Let B = b * M and
A = a * M
The count of numbers divisible by
'M' between A and B will be equal
to b - a.
Example:
A = 25, B = 70, M = 10.
Now, a = 2, b = 7.
Count = 7 - 2 = 5.
It can be observed that, if A is divisible by M, 'b - a' will exclude the count for A, so the count will be less by 1. Thus, in this case we add 1 explicitly.
Example when A is divisible by M:
A = 30, B = 70, M = 10.
Now, a = 3, b = 7.
Count = 7 - 3 = 4.
But, Count should be 5. Thus, we will
add 1 explicitly.
Below is the implementation of the above method :
C++
// C++ program to count the numbers divisible by
// M in a given range
#include <bits/stdc++.h>
using namespace std;
// Function to count the numbers divisible by
// M in a given range
int countDivisibles(int A, int B, int M)
{
// Add 1 explicitly as A is divisible by M
if (A % M == 0)
return (B / M) - (A / M) + 1;
// A is not divisible by M
return (B / M) - (A / M);
}
// driver program
int main()
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
cout << (countDivisibles(A, B, M));
}
// This code is contributed by subham348.
// Java program to count the numbers divisible by
// M in a given range
import java.io.*;
class GFG {
// Function to count the numbers divisible by
// M in a given range
static int countDivisibles(int A, int B, int M)
{
// Add 1 explicitly as A is divisible by M
if (A % M == 0)
return (B / M) - (A / M) + 1;
// A is not divisible by M
return (B / M) - (A / M);
}
// driver program
public static void main(String[] args)
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
System.out.println(countDivisibles(A, B, M));
}
}
// Contributed by Pramod Kumar
# Program to count the numbers divisible
# by M in a given range
# Returns count of numbers in [A B] that
# are divisible by M.
def countDivisibles(A, B, M):
# Add 1 explicitly as A is divisible by M
if (A % M == 0):
return ((B / M) - (A / M)) + 1
# A is not divisible by M
return ((B / M) - (A / M))
# Driver Code
# A and B define the range, M
# is the dividend
A = 30
B = 70
M = 10
# Printing the result
print(countDivisibles(A, B, M))
# This code is contributed by Sam007
// C# program to count the numbers
// divisible by M in a given range
using System;
public class GFG {
// Function to count the numbers divisible by
// M in a given range
static int countDivisibles(int A, int B, int M)
{
// Add 1 explicitly as A is divisible by M
if (A % M == 0)
return (B / M) - (A / M) + 1;
// A is not divisible by M
return (B / M) - (A / M);
}
// driver program
public static void Main()
{
// A and B define the range, M is the dividend
int A = 30, B = 100, M = 30;
// Printing the result
Console.WriteLine(countDivisibles(A, B, M));
}
}
// This code is contributed by Sam007
<?php
// PHP Program to count the numbers
// divisible by M in a given range
// Returns count of numbers in
// [A B] that are divisible by M.
function countDivisibles($A, $B, $M)
{
// Add 1 explicitly as A
// is divisible by M
if ($A % $M == 0)
return ($B / $M) -
($A / $M) + 1;
// A is not divisible by M
return ($B / $M) -
($A / $M);
}
// Driver Code
// A and B define the range,
// M is the dividend
$A = 30;
$B = 70;
$M = 10;
// Printing the result
echo countDivisibles($A, $B, $M) ;
return 0;
// This code is contributed by nitin mittal.
?>
// Javascript Program to count the numbers
// divisible by M in a given range
// Returns count of numbers in
// [A B] that are divisible by M.
function countDivisibles(A, B, M)
{
// Add 1 explicitly as A
// is divisible by M
if (A % M == 0)
return (B / M) -
(A / M) + 1;
// A is not divisible by M
return (B / M) -
(A / M);
}
// Driver Code
// A and B define the range,
// M is the dividend
let A = 30;
let B = 70;
let M = 10;
// Printing the result
document.write(countDivisibles(A, B, M));
// This code is contributed by gfgking
Time Complexity: O(1)
Auxiliary Space: O(1)
Similar Reads
Sum of all numbers in the given range which are divisible by M
Given three numbers A, B and M such that A < B, the task is to find the sum of numbers divisible by M in the range [A, B]. Examples: Input: A = 25, B = 100, M = 30 Output: 180 Explanation: In the given range [25, 100] 30, 60 and 90 are the numbers which are divisible by M = 30 Therefore, sum of t
15 min read
Sum of all numbers divisible by 6 in a given range
Given a range L-R, find the sum of all numbers divisible by 6 in range L-RL and R are very large.Examples: Input : 1 20 Output : 36 Explanation: 6 + 12 + 18 = 36 Input : 5 7 Output : 6 Explanation: 6 is the only divisible number in range 5-7 A naive approach is be to run a loop from L to R and sum u
6 min read
Find the count of distinct numbers in a range
Given an array of size N containing numbers only from 0 to 63, and you are asked Q queries regarding it.Queries are as follows: 1 X Y i.e Change the element at index X to Y2 L R i.e Print the count of distinct elements present in between L and R inclusive Examples: Input: N = 7 ar = {1, 2, 1, 3, 1,
15 min read
Count of numbers upto M divisible by given Prime Numbers
Given an array arr[] of Prime Numbers and a number M, the task is to count the number of elements in the range [1, M] that are divisible by any of the given prime numbers. Examples: Input: arr[] = {2, 3, 5, 7} M = 100 Output: 78 Explanation:In total there are 78 numbers that are divisible by either
5 min read
Count of numbers with all digits same in a given range
Given two integers L and R denoting the starting and end values of a range, the task is to count all numbers in that range whose all digit are same, like 1, 22, 444, 3333, etc.Example: Input: L = 12, R = 68 Output: 5 Explanation: { 22, 33, 44, 55, 66} are the numbers with same digits in the given ra
10 min read
Count numbers with unit digit k in given range
Here given a range from low to high and given a number k.You have to find out the number of count which a number has same digit as kExamples: Input: low = 2, high = 35, k = 2 Output: 4 Numbers are 2, 12, 22, 32 Input: low = 3, high = 30, k = 3 Output: 3 Numbers are 3, 13, 23 A naive approach is to t
7 min read
Count numbers in a range that are divisible by all array elements
Given N numbers and two numbers L and R, the task is to print the count of numbers in the range [L, R] which are divisible by all the elements of the array. Examples: Input: a[] = {1, 4, 2], L = 1, R = 10 Output : 2 In range [1, 10], the numbers 4 and 8 are divisible by all the array elements. Input
8 min read
Count n digit numbers divisible by given number
Given number of digit n and a number, the task is to count all the numbers which are divisible by that number and having n digit. Examples : Input : n = 2, number = 7Output : 13Explanation: There are nine n digit numbers that are divisible by 7. Numbers are 14, 21, 28, 35, 42, 49, .... 91, 98 Input
8 min read
Count of Double Prime numbers in a given range L to R
Given two integers L and R, the task to find the number of Double Prime numbers in the range. A number N is called double prime when the count of prime numbers in the range 1 to N (excluding 1 and including N) is also prime. Examples: Input: L = 3, R = 10 Output: 4 Explanation: For 3, we have the ra
9 min read
Count numbers in range 1 to N which are divisible by X but not by Y
Given two positive integers X and Y, the task is to count the total numbers in range 1 to N which are divisible by X but not Y. Examples: Input: x = 2, Y = 3, N = 10 Output: 4 Numbers divisible by 2 but not 3 are : 2, 4, 8, 10 Input : X = 2, Y = 4, N = 20 Output : 5 Numbers divisible by 2 but not 4
10 min read