# Count pair in an array whose product is divisible by k in Python

In this article, we will learn how to count the pair in an array whose product is divisible by k in Python.

Examples

Input: arr[] = {2, 3, 5, 8, 9} k = 4 Output: 4 Explanation: (2, 8), (3, 8), (5, 8), (9, 8) these are the possible pair that are divisible by given k vaule. Input: arr[] = {2, 1, 3} k = 4 Output: No possible pairs

## Number of pair in an array whose product is divisible by k in Python

1. We are going to solve this problem using two nested loops.

2. Declare a variable count to store the result.

3. Iterate the array from range 0 to n as an outer loop

- Iterate the array from the range i+1 to n as an inner loop
- Now check if (arr[i]*arr[j]%k == 0) then increase count 1.

4. Finally, return the count.

def countPairs(arr, n, k): count = 0 for i in range(n): for j in range(i+1, n): if (arr[i]*arr[j]%k == 0): count += 1 return count arr = [2, 3, 5, 8, 9, 7, 10, 12] n = len(arr) k = int(input("Enter the k value: ")) result = countPairs(arr, n, k) if(result>0): print("Number of pair in an array whose product is divisible by k is ",result) else: print("No possible pairs")

Output

Enter the k value: 4 Number of pair in an array whose product is divisible by k is 14 Enter the k value: 11 No possible pairs

Also, read

- Python program to find pair with the greatest product in an array
- Finding largest triplet product in a stream in Python

This is a brute force approach, can it be done in an optimised way?

Is there any to find an approach that can solve this problem less than O(n**2)