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

1. The function count_divisible takes four parameters: start, last, x, and y.
2. We initialize counter to 0 to count the divisible numbers between start and last.
3. If start is greater than last, we swap their values to ensure that start is smaller than or equal to last.
4. We start the iteration from start to last, checking each number in the range.
5. If a number num is divisible by both x and y, we increment the counter, print the number, and move to the next number.
6. We use the counter value to decide whether to increment num by x or y.
7. If counter is greater than 0, we increment num by the smaller of x and y.
8. If counter is 0, it means we haven't found any divisible number yet, so we simply increment num by 1.
9. 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
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// 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;
}

 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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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.