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.

Categories
Relative Post