Posted on by Kalkicode
Code Array

Count divisible pairs in an array

In the realm of coding challenges, a common problem is to count divisible pairs in an array. Given an array of integers, the task is to identify pairs of elements that are divisible by each other and then count the total number of such pairs. This problem finds its applications in various domains such as data analysis, competitive programming, and algorithmic research.

Problem Statement and Description

Consider an array of integers: [5, 8, 2, 4, 9, 3]. The goal is to find and count pairs of elements in the array that are divisible by each other. In other words, for each pair (i, j), if collection[i] is divisible by collection[j] or collection[j] is divisible by collection[i], the pair qualifies as a divisible pair.

Example

For the given array [5, 8, 2, 4, 9, 3], there are four divisible pairs: (8, 2), (8, 4), (4, 2), and (9, 3).

Idea to Solve the Problem

To solve this problem, a brute force approach can be used. For each pair of elements (i, j) in the array, check if either collection[i] is divisible by collection[j] or collection[j] is divisible by collection[i]. If this condition is met, increment the count of divisible pairs.

Standard Pseudocode

divisible_pair(collection[], size)
    result = 0
    for i = 0 to size - 2
        for j = i + 1 to size - 1
            if collection[i] % collection[j] == 0 or collection[j] % collection[i] == 0
                result++
    print "Total divisible pairs:", result

Algorithm Explanation

  1. Initialize result to 0 to store the count of divisible pairs.
  2. Iterate through each pair of elements (i, j) in the array using nested loops.
  3. For each pair, check if either collection[i] is divisible by collection[j] or collection[j] is divisible by collection[i].
  4. If the above condition is satisfied, increment the result counter.
  5. After iterating through all pairs, print the total count of divisible pairs.

Code Solution

//C++ Program 
//Count divisible pairs in an array
#include <stdio.h>

//Function which is counting all divisible pairs
void divisible_pair(int collection[],int size)
{
  int result = 0;

  for (int i = 0; i < size; ++i)
  {
    for (int j = i+1; j < size; ++j)
    {
      //Check if  [i] and [j] element are divisible ?
      if(collection[i]%collection[j]==0 || collection[j]%collection[i]==0)
      {
        result++;
      }
    }
  }
  printf("Total divisible pairs : %d\n",result );

}
int main()
{
  //Define array elements
  int collection[]={5,8,2,4,9,3};

  //Get the size of array
  int size=sizeof(collection)/sizeof(collection[0]);

  divisible_pair(collection,size);
  
  return 0;
}

Output

Total divisible pairs : 4
/*
  C++ Program
  Count divisible pairs in an array
*/
#include<iostream>
using namespace std;

class MyArray {
	public:

		//Function which is counting all divisible pairs
		void divisible_pair(int collection[], int size) {
			int result = 0;
			for (int i = 0; i < size; ++i) {
				for (int j = i + 1; j < size; ++j) {
					//Check if  [i] and [j] element are divisible ?

					if (collection[i] % collection[j] == 0 || collection[j] % collection[i] == 0) {
						result++;
					}
				}
			}
			cout << " Total divisible pairs : " << result << "\n";
		}
};
int main() {
	MyArray obj ;
	//Define array elements
	int collection[] = {
		5,
		8,
		2,
		4,
		9,
		3
	};
	//Get the size of array
	int size = sizeof(collection) / sizeof(collection[0]);
	obj.divisible_pair(collection, size);
	return 0;
}

Output

 Total divisible pairs : 4
/*
  Java Program
  Count divisible pairs in an array
*/
public class MyArray {
  //Function which is counting all divisible pairs
  public void divisible_pair(int []collection,int size)
  {
    int result = 0;

    for (int i = 0; i < size; ++i)
    {
      for (int j = i+1; j < size; ++j)
      {
        //Check if  [i] and [j] element are divisible ?
        if(collection[i]%collection[j]==0 || collection[j]%collection[i]==0)
        {
          result++;
        }
      }
    }
    System.out.print(" Total divisible pairs :  "+result+"\n" );

  }

  public static void main(String[] args) 
  {
  

    MyArray obj = new MyArray();
    //Define array elements
    int collection[]={5,8,2,4,9,3};

    //Get the size of array
    int size=collection.length;

    obj.divisible_pair(collection,size);

  }
}

Output

 Total divisible pairs : 4
/*
  C# Program
  Count divisible pairs in an array
*/
using System;

public class MyArray {
	//Function which is counting all divisible pairs
	public void divisible_pair(int[] collection, int size) {
		int result = 0;
		for (int i = 0; i < size; ++i) {
			for (int j = i + 1; j < size; ++j) {
				//Check if  [i] and [j] element are divisible ?

				if (collection[i] % collection[j] == 0 || collection[j] % collection[i] == 0) {
					result++;
				}
			}
		}
		Console.Write(" Total divisible pairs : " + result + "\n");
	}
	public static void Main(String[] args) {
		MyArray obj = new MyArray();
		//Define array elements
		int []collection = {
			5,
			8,
			2,
			4,
			9,
			3
		};
		//Get the size of array
		int size = collection.Length;
		obj.divisible_pair(collection, size);
	}
}

Output

 Total divisible pairs : 4
<?php
/*
  Php Program
  Count divisible pairs in an array
*/
class MyArray {
	//Function which is counting all divisible pairs

	public 	function divisible_pair($collection, $size) {
		$result = 0;
		for ($i = 0; $i < $size; ++$i) {
			for ($j = $i + 1; $j < $size; ++$j) {
				//Check if  [i] and [j] element are divisible ?

				if ($collection[$i] % $collection[$j] == 0 || $collection[$j] % $collection[$i] == 0) {
					$result++;
				}
			}
		}
		echo(" Total divisible pairs : ". $result ."\n");
	}
}

function main() {
	$obj = new MyArray();
	//Define array elements
	$collection = array(5, 8, 2, 4, 9, 3);
	//Get the size of array
	$size = count($collection);
	$obj->divisible_pair($collection, $size);

}
main();

Output

 Total divisible pairs : 4
/*
  Node Js Program
  Count divisible pairs in an array
*/
class MyArray {
	//Function which is counting all divisible pairs
	divisible_pair(collection, size) {
		var result = 0;
		for (var i = 0; i < size; ++i) {
			for (var j = i + 1; j < size; ++j) {
				//Check if  [i] and [j] element are divisible ?

				if (collection[i] % collection[j] == 0 || collection[j] % collection[i] == 0) {
					result++;
				}
			}
		}

		process.stdout.write(" Total divisible pairs : " + result + "\n");
	}
}

function main(args) {
	var obj = new MyArray();
	//Define array elements
	var collection = [5, 8, 2, 4, 9, 3];
	//Get the size of array
	var size = collection.length;
	obj.divisible_pair(collection, size);
}

main();

Output

 Total divisible pairs : 4
# Python 3 Program
# Count divisible pairs in an array
class MyArray :
	# Function which is counting all divisible pairs
	def divisible_pair(self, collection, size) :
		result = 0
		i = 0
		while (i < size) :
			j = i + 1
			while (j < size) :
				# Check if  [i] and [j] element are divisible ?

				if (collection[i] % collection[j] == 0 or collection[j] % collection[i] == 0) :
					result += 1
				
				j += 1
			
			i += 1
		
		print(" Total divisible pairs : ", result ,"\n", end = "")
	

def main() :
	obj = MyArray()
	collection = [5, 8, 2, 4, 9, 3]
	size = len(collection)
	obj.divisible_pair(collection, size)


if __name__ == "__main__":
	main()

Output

 Total divisible pairs :  4
# Ruby Program
# Count divisible pairs in an array
class MyArray 
	# Function which is counting all divisible pairs
	def divisible_pair(collection, size) 
		result = 0
		i = 0
		while (i < size) 
			j = i + 1
			while (j < size) 
				# Check if  [i] and [j] element are divisible ?

				if (collection[i] % collection[j] == 0 || collection[j] % collection[i] == 0) 
					result += 1
				end
				j += 1
			end
			i += 1
		end
		print(" Total divisible pairs  :", result ,"\n")
	end
end
def main() 
	obj = MyArray.new()
	collection = [5, 8, 2, 4, 9, 3]
	size = collection.length
	obj.divisible_pair(collection, size)
end
main()

Output

 Total divisible pairs  :4
/*
  Scala Program
  Count divisible pairs in an array
*/
class MyArray {
	//Function which is counting all divisible pairs
	def divisible_pair(collection: Array[Int], size: Int): Unit = {
		var result: Int = 0;
		var i: Int = 0;
		while (i < size) {
			var j: Int = i + 1;
			while (j < size) {
				//Check if  [i] and [j] element are divisible?

				if (collection(i) % collection(j) == 0 || collection(j) % collection(i) == 0) {
					result += 1;
				}
				j += 1;
			}
			i += 1;
		}
		print(" Total divisible pairs : " + result + "\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyArray = new MyArray();
		val collection: Array[Int] = Array(5, 8, 2, 4, 9, 3);
		val size: Int = collection.length;
		obj.divisible_pair(collection, size);
	}
}

Output

 Total divisible pairs : 4
/*
  Swift Program
  Count divisible pairs in an array
*/
class MyArray {
	//Function which is counting all divisible pairs
	func divisible_pair(_ collection: [Int], _ size: Int) {
		var result: Int = 0;
		var i: Int = 0;
		while (i < size) {
			var j: Int = i + 1;
			while (j < size) {
				//Check if  [i] and [j] element are divisible?

				if (collection[i] % collection[j] == 0 || collection[j] % collection[i] == 0) {
					result += 1;
				}
				j += 1;
			}
			i += 1;
		}
		print(" Total divisible pairs : ", result ,"\n", terminator: "");
	}
}
func main() {
	let obj: MyArray = MyArray();
	let collection: [Int] = [5, 8, 2, 4, 9, 3];
	let size: Int = collection.count;
	obj.divisible_pair(collection, size);
}
main();

Output

 Total divisible pairs :  4

Resultant Output Explanation

For the input array [5, 8, 2, 4, 9, 3], the algorithm processes the following pairs:

  • (5, 8) - Not divisible
  • (5, 2) - Not divisible
  • (5, 4) - Not divisible
  • (5, 9) - Not divisible
  • (5, 3) - Not divisible
  • (8, 2) - Divisible
  • (8, 4) - Divisible
  • (8, 9) - Not divisible
  • (8, 3) - Not divisible
  • (2, 4) - Divisible
  • (2, 9) - Not divisible
  • (2, 3) - Not divisible
  • (4, 9) - Not divisible
  • (4, 3) - Not divisible
  • (9, 3) - Divisible

The algorithm identifies and counts four divisible pairs: (8, 2), (8, 4), (4, 2), and (9, 3).

Time Complexity

The algorithm utilizes nested loops to compare each pair of elements in the array. For an array of size 'n', the outer loop runs (n - 1) times, and the inner loop runs (n - 2) times on average. Therefore, the time complexity can be approximated as O(n^2), indicating a quadratic time complexity.

Comment

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