How to Count pairs whose products exist in array in Python
In this tutorial, we will learn How to Count pairs whose products exist in an array in Python using Brute Force as well as a Time-Efficient Approach.
Brute Force Approach: Count pairs whose products exist in array
First, we can simply iterate over the list using two for loops to find out all the pairs. Then we find their products and use another loop to check if the product exists in the list. If it does, we increment the counter and append the pair to the pair list. This is a Naive Approach and will give a worst-case complexity of O(n3).
Python Implementation
The following code shows the implementation of the above steps in Python.
def countPairs(my_list): count = 0 pairs = [] # Generate all pairs of the lists for i in range(len(my_list)): for j in range(i + 1, len(my_list)): product = my_list[i] * my_list[j] # if product exists in my_list # increment count # append the pair to pairs for k in range (len(my_list)): if (my_list[k] == product): count += 1 pairs.append((my_list[i], my_list[j])) break print(pairs) return count my_list = [3, 18, 6, 9, 2, 24, 4] print(countPairs(my_list))
INPUT my_list: [3, 18, 6, 9, 2, 24, 4] OUTPUT pairs: [(3, 6), (3, 2), (6, 4), (9, 2)] count: 4 INPUT my_list: [2, 5, 3, 4, 15, 24, 12, 6, 8] OUTPUT pairs: [(2, 3), (2, 4), (2, 12), (2, 6), (5, 3), (3, 4), (3, 8), (4, 6)] count: 8
Time Efficient Approach: Count pairs whose products exist in array
Here we try to reduce the complexity.
Upon a little pondering, we come to the conclusion that we can reduce the complexity by eliminating the third loop in two ways, and they are:
- by using a set to store the elements.
- by creating a list of the product of all the pairs
Using a Set to Store the Elements
Set in Python is a special type of Data Structure that contains an unordered collection of unique elements.
We can simply check if the element exists in the set in O(1) time. Therefore, we can reduce the time complexity from O(n3) to O(n2). Hence, making it more time-efficient.
Python Implementation
The following code shows the implementation of the above steps in Python.
def countPairs(my_list): count = 0 # Create an empty set elements = set() # Insert all the elements into set for i in range(len(my_list)): elements.add(my_list[i]) pairs = [] # Generate all pairs of the lists for i in range(len(my_list)): for j in range(i + 1, len(my_list)): product = my_list[i] * my_list[j] # if product exists in elements # increment count # append the pair to pairs if product in(elements): count += 1 pairs.append((my_list[i], my_list[j])) print(pairs) return count my_list = [2, 4, 6, 8, 3, 15, 5] print(countPairs(my_list))
INPUT my_list: [2, 4, 6, 8, 3, 15, 5] OUTPUT pairs: [(2, 4), (2, 3), (3, 5)] count: 3 INPUT my_list: [2, 4, 15, 24, 12, 6, 8] OUTPUT pairs: [(2, 4), (2, 12), (2, 6), (4, 6)] count: 4
Creating a List of the Product of all the Pairs
Here we first use two nested for loops to get the product of each pair and append it to the products list. Then we use another pair of loops to iterate over the product list and the original list. If an element in the product list matches to any element in the original list we increment the counter. As we use 2 nested for loops, this solution also has a Time Complexity of O(n2).
Python Implementation
The following code shows the implementation of the above steps in Python.
def countPairs(my_list): count = 0 product = [] # Generate all product pairs of the my_list # Append them to the product list for i in range(len(my_list)): for j in range(i + 1, len(my_list)): product. append(my_list[i] * my_list[j]) # if product exists in my_list increment count for i in range (len(product)): for j in range(len(my_list)): if (product[i] == my_list[j]): count += 1 break return count my_list = [2, 3, 15, 18, 16, 6, 8] print("No. of pairs: ",countPairs(my_list))
INPUT my_list: [2, 3, 15, 18, 16, 6, 8] OUTPUT No. of pairs: 3 INPUT my_list: [2, 4, 15, 24, 12, 6, 8] OUTPUT No. of pairs: 4
You may also like: All Possible Pairs in a List with a given sum and All possible sublists of a list in Python
Leave a Reply