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

2 responses to “Count pair in an array whose product is divisible by k in Python”

1. Shivam says:

   August 8, 2021 at 5:29 pm

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

   Reply
2. Phanee says:

   February 20, 2022 at 10:32 am

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

   Reply