# 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:

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(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)):
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```