Count of common divisible of two numbers in a range
The given problem is to find the count of common divisible numbers between two given integers x
and
y
within a given range [start, last]
. In other words, we need to determine how many
numbers in the range are divisible by both x
and y
.
Problem Statement
Given two integers x
and y
, and a range [start, last]
, we need to find and
count all the numbers within the range that are divisible by both x
and y
.
Example
Let's take the range from 1 to 50 and consider x = 4
and y = 3
.
Step 1: Initialize counter = 0
to count the divisible numbers.
Step 2: Start iterating through the numbers from start
to last
(i.e., 1 to 50).
Step 3: Check if the current number num
is divisible by both x
and y
using
the condition num % x == 0 && num % y == 0
.
Step 4: If the condition is true, increment the counter
and print the current number.
Step 5: Continue the iteration until all the numbers in the given range are checked.
Step 6: Display the final count stored in counter
.
Pseudocode
count_divisible(start, last, x, y):
counter = 0
if start > last:
swap start and last
print "Divisible by (", x, ",", y, ") in range of [", start, "-", last, "] are ["
num = start
while num <= last:
if num % x == 0 && num % y == 0:
print num
counter++
if counter > 0:
if x > y:
num += x
else:
num += y
else:
num++
print "]"
print "Counter :", counter
Algorithm Explanation
- The function
count_divisible
takes four parameters:start
,last
,x
, andy
. - We initialize
counter
to 0 to count the divisible numbers betweenstart
andlast
. - If
start
is greater thanlast
, we swap their values to ensure thatstart
is smaller than or equal tolast
. - We start the iteration from
start
tolast
, checking each number in the range. - If a number
num
is divisible by bothx
andy
, we increment thecounter
, print the number, and move to the next number. - We use the
counter
value to decide whether to incrementnum
byx
ory
. - If
counter
is greater than 0, we incrementnum
by the smaller ofx
andy
. - If
counter
is 0, it means we haven't found any divisible number yet, so we simply incrementnum
by 1. - After processing all numbers in the range, we print the final count of divisible numbers stored in
counter
.
Code Solution
Here given code implementation process.
// C program
// Count of common divisible of two numbers in a range
#include <stdio.h>
// Count all divisible numbers of x and y in given range
void count_divisible(int start, int last, int x, int y)
{
int counter = 0;
if (start > last)
{
//Change sequence
count_divisible(last, start, x, y);
return;
}
//Display calculated result
printf("\n Divisible by (%d,%d) in range of [%d-%d] are \n [", x, y, start, last);
int num = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
printf(" %d", num);
//When x and y are divisible by num
counter++;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num++;
}
}
//Display calculated result
printf(" ]\n Counter : %d\n", counter);
}
int main()
{
//Test case
int x = 4;
int y = 3;
count_divisible(1, 50, x, y);
x = 3;
y = 7;
count_divisible(50, 150, x, y);
x = 2;
y = 5;
count_divisible(1, 100, x, y);
x = 2;
y = 7;
count_divisible(1, 12, x, y);
return 0;
}
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
/*
Java program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
public void count_divisible(int start, int last, int x, int y)
{
int counter = 0;
if (start > last)
{
//Change sequence
count_divisible(last, start, x, y);
return;
}
//Display calculated result
System.out.print("\n Divisible by (" + x + "," + y + ") in range of [" + start + "-" + last + "] are \n [");
int num = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
System.out.print(" " + num);
//When x and y are divisible by num
counter++;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num++;
}
}
//Display calculated result
System.out.print(" ]\n Counter : " + counter + "\n");
}
public static void main(String[] args)
{
Divisor obj = new Divisor();
//Test case
int x = 4;
int y = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
}
}
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Count of common divisible of two numbers in a range
*/
class Divisor
{
public:
// Count all divisible numbers of x and y in given range
void count_divisible(int start, int last, int x, int y)
{
int counter = 0;
if (start > last)
{
//Change sequence
this->count_divisible(last, start, x, y);
return;
}
//Display calculated result
cout << "\n Divisible by (" << x << "," << y << ") in range of [" << start << "-" << last << "] are \n [";
int num = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
cout << " " << num;
//When x and y are divisible by num
counter++;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num++;
}
}
//Display calculated result
cout << " ]\n Counter : " << counter << "\n";
}
};
int main()
{
Divisor obj = Divisor();
//Test case
int x = 4;
int y = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
return 0;
}
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
//Include namespace system
using System;
/*
C# program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
public void count_divisible(int start, int last, int x, int y)
{
int counter = 0;
if (start > last)
{
//Change sequence
count_divisible(last, start, x, y);
return;
}
//Display calculated result
Console.Write("\n Divisible by (" + x + "," + y + ") in range of [" + start + "-" + last + "] are \n [");
int num = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
Console.Write(" " + num);
//When x and y are divisible by num
counter++;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num++;
}
}
//Display calculated result
Console.Write(" ]\n Counter : " + counter + "\n");
}
public static void Main(String[] args)
{
Divisor obj = new Divisor();
//Test case
int x = 4;
int y = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
}
}
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
<?php
/*
Php program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
public function count_divisible($start, $last, $x, $y)
{
$counter = 0;
if ($start > $last)
{
//Change sequence
$this->count_divisible($last, $start, $x, $y);
return;
}
//Display calculated result
echo "\n Divisible by (". $x .",". $y .") in range of [". $start ."-". $last ."] are \n [";
$num = $start;
while ($num <= $last)
{
if ($num % $x == 0 && $num % $y == 0)
{
echo " ". $num;
//When x and y are divisible by num
$counter++;
}
if ($counter > 0)
{
//Increase count value
if ($x > $y)
{
$num += $x;
}
else
{
$num += $y;
}
}
else
{
//When not get first divisible number
$num++;
}
}
//Display calculated result
echo " ]\n Counter : ". $counter ."\n";
}
}
function main()
{
$obj = new Divisor();
//Test case
$x = 4;
$y = 3;
//range (1-50)
$obj->count_divisible(1, 50, $x, $y);
$x = 3;
$y = 7;
//range (50-150)
$obj->count_divisible(50, 150, $x, $y);
$x = 2;
$y = 5;
//range (1-100)
$obj->count_divisible(1, 100, $x, $y);
$x = 2;
$y = 7;
//range (1-12)
$obj->count_divisible(1, 12, $x, $y);
}
main();
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
/*
Node Js program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
count_divisible(start, last, x, y)
{
var counter = 0;
if (start > last)
{
//Change sequence
this.count_divisible(last, start, x, y);
return;
}
//Display calculated result
process.stdout.write("\n Divisible by (" + x + "," + y + ") in range of [" + start + "-" + last + "] are \n [");
var num = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
process.stdout.write(" " + num);
//When x and y are divisible by num
counter++;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num++;
}
}
//Display calculated result
process.stdout.write(" ]\n Counter : " + counter + "\n");
}
}
function main()
{
var obj = new Divisor();
//Test case
var x = 4;
var y = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
}
main();
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
# Python 3 program
# Count of common divisible of two numbers in a range
class Divisor :
# Count all divisible numbers of x and y in given range
def count_divisible(self, start, last, x, y) :
counter = 0
if (start > last) :
# Change sequence
self.count_divisible(last, start, x, y)
return
# Display calculated result
print("\n Divisible by (", x ,",", y ,") in range of [", start ,"-", last ,"] are \n [", end = "")
num = start
while (num <= last) :
if (num % x == 0 and num % y == 0) :
print(" ", num, end = "")
# When x and y are divisible by num
counter += 1
if (counter > 0) :
# Increase count value
if (x > y) :
num += x
else :
num += y
else :
# When not get first divisible number
num += 1
# Display calculated result
print(" ]\n Counter : ", counter ,"\n", end = "")
def main() :
obj = Divisor()
# Test case
x = 4
y = 3
# range (1-50)
obj.count_divisible(1, 50, x, y)
x = 3
y = 7
# range (50-150)
obj.count_divisible(50, 150, x, y)
x = 2
y = 5
# range (1-100)
obj.count_divisible(1, 100, x, y)
x = 2
y = 7
# range (1-12)
obj.count_divisible(1, 12, x, y)
if __name__ == "__main__": main()
Output
Divisible by ( 4 , 3 ) in range of [ 1 - 50 ] are
[ 12 24 36 48 ]
Counter : 4
Divisible by ( 3 , 7 ) in range of [ 50 - 150 ] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by ( 2 , 5 ) in range of [ 1 - 100 ] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by ( 2 , 7 ) in range of [ 1 - 12 ] are
[ ]
Counter : 0
# Ruby program
# Count of common divisible of two numbers in a range
class Divisor
# Count all divisible numbers of x and y in given range
def count_divisible(start, last, x, y)
counter = 0
if (start > last)
# Change sequence
self.count_divisible(last, start, x, y)
return
end
# Display calculated result
print("\n Divisible by (", x ,",", y ,") in range of [", start ,"-", last ,"] are \n [")
num = start
while (num <= last)
if (num % x == 0 && num % y == 0)
print(" ", num)
# When x and y are divisible by num
counter += 1
end
if (counter > 0)
# Increase count value
if (x > y)
num += x
else
num += y
end
else
# When not get first divisible number
num += 1
end
end
# Display calculated result
print(" ]\n Counter : ", counter ,"\n")
end
end
def main()
obj = Divisor.new()
# Test case
x = 4
y = 3
# range (1-50)
obj.count_divisible(1, 50, x, y)
x = 3
y = 7
# range (50-150)
obj.count_divisible(50, 150, x, y)
x = 2
y = 5
# range (1-100)
obj.count_divisible(1, 100, x, y)
x = 2
y = 7
# range (1-12)
obj.count_divisible(1, 12, x, y)
end
main()
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
/*
Scala program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
def count_divisible(start: Int, last: Int, x: Int, y: Int): Unit = {
var counter: Int = 0;
if (start > last)
{
//Change sequence
count_divisible(last, start, x, y);
return;
}
//Display calculated result
print("\n Divisible by (" + x + "," + y + ") in range of [" + start + "-" + last + "] are \n [");
var num: Int = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
print(" " + num);
//When x and y are divisible by num
counter += 1;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num += 1;
}
}
//Display calculated result
print(" ]\n Counter : " + counter + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Divisor = new Divisor();
//Test case
var x: Int = 4;
var y: Int = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
}
}
Output
Divisible by (4,3) in range of [1-50] are
[ 12 24 36 48 ]
Counter : 4
Divisible by (3,7) in range of [50-150] are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by (2,5) in range of [1-100] are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by (2,7) in range of [1-12] are
[ ]
Counter : 0
/*
Swift 4 program
Count of common divisible of two numbers in a range
*/
class Divisor
{
// Count all divisible numbers of x and y in given range
func count_divisible(_ start: Int, _ last: Int, _ x: Int, _ y: Int)
{
var counter: Int = 0;
if (start > last)
{
//Change sequence
self.count_divisible(last, start, x, y);
return;
}
//Display calculated result
print("\n Divisible by (", x ,",", y ,") in range of [", start ,"-", last ,"]are \n [", terminator: "");
var num: Int = start;
while (num <= last)
{
if (num % x == 0 && num % y == 0)
{
print(" ", num, terminator: "");
//When x and y are divisible by num
counter += 1;
}
if (counter > 0)
{
//Increase count value
if (x > y)
{
num += x;
}
else
{
num += y;
}
}
else
{
//When not get first divisible number
num += 1;
}
}
//Display calculated result
print(" ]\n Counter : ", counter ,"\n", terminator: "");
}
}
func main()
{
let obj: Divisor = Divisor();
//Test case
var x: Int = 4;
var y: Int = 3;
//range (1-50)
obj.count_divisible(1, 50, x, y);
x = 3;
y = 7;
//range (50-150)
obj.count_divisible(50, 150, x, y);
x = 2;
y = 5;
//range (1-100)
obj.count_divisible(1, 100, x, y);
x = 2;
y = 7;
//range (1-12)
obj.count_divisible(1, 12, x, y);
}
main();
Output
Divisible by ( 4 , 3 ) in range of [ 1 - 50 ]are
[ 12 24 36 48 ]
Counter : 4
Divisible by ( 3 , 7 ) in range of [ 50 - 150 ]are
[ 63 84 105 126 147 ]
Counter : 5
Divisible by ( 2 , 5 ) in range of [ 1 - 100 ]are
[ 10 20 30 40 50 60 70 80 90 100 ]
Counter : 10
Divisible by ( 2 , 7 ) in range of [ 1 - 12 ]are
[ ]
Counter : 0
Resultant Output Explanation
The provided code is running the function count_divisible
for four different test cases with different
values of x
, y
, start
, and last
. The output shows the numbers in
the given range that are divisible by both x
and y
, along with the count of such numbers.
For example, in the first test case with x = 4
and y = 3
, the numbers divisible by both 4
and 3 in the range [1-50] are 12, 24, 36, and 48. The total count of such numbers is 4.
Time Complexity
The time complexity of the provided code is O(N), where N is the number of elements in the given range
[start, last]
. In the worst case, the code will iterate through all the numbers in the given range
once. The loop's complexity is directly proportional to the size of the range, so the time complexity is linear.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment