Count pair in an array whose product is divisible by k in Python
By Abinash ReddyIn 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 pairsNumber 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
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)