How to Count pairs whose products exist in array in Python

By Nishtha Grover

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(n³).

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:

1. by using a set to store the elements.
2. 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(n³) to O(n²). 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(n²). 

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