💡 Problem Formulation: We’re tackling the issue of how to calculate the number of quadruples within a list where the product of the first pair and the product of the last pair are identical. For example, given a list [1, 6, 2, 6, 1], the quadruple (1,6,6,1) satisfies this condition as 1*6 equals 1*6.
Method 1: Brute Force Approach
This method involves checking each possible quadruple in the list. It’s a straightforward approach that iterates over all combinations of numbers and compares the product of the first and last pairs. Great for small lists but inefficient for larger ones due to its O(n^4) complexity.
Here’s an example:
def find_quadruples(lst):
count = 0
for i in range(len(lst)):
for j in range(i+1, len(lst)):
for k in range(j+1, len(lst)):
for l in range(k+1, len(lst)):
if lst[i] * lst[j] == lst[k] * lst[l]:
count += 1
return count
example_list = [1, 6, 2, 6, 1]
print(find_quadruples(example_list))Output: 3
This code snippet sets up four nested loops, each scanning through the list indices. It then checks if the product of the first pair (lst[i] * lst[j]) and the second pair (lst[k] * lst[l]) are equal, incrementing the count if they are. Finally, it returns the total count.
Method 2: Using Dictionary for Two-Sum Pairs
This method optimizes the brute force approach by storing two-sum products in a dictionary. The key insight is that we can map products to a list of index pairs that produce that product. This reduces the overall complexity to O(n^2).
Here’s an example:
from collections import defaultdict
def find_quadruples(lst):
product_map = defaultdict(int)
count = 0
for i in range(len(lst)):
for j in range(i+1, len(lst)):
product_map[lst[i] * lst[j]] += 1
for product, frequency in product_map.items():
count += frequency * (frequency - 1) // 2
return count
example_list = [1, 6, 2, 6, 1]
print(find_quadruples(example_list))Output: 3
This snippet creates a defaultdict to track products of pairs. On the first pass, it populates this dictionary with the frequency of each product. The second pass calculates the count by adding combinations of pairs (quadruples) that have the same product.
Method 3: Hash Table with Pairs as Keys
Instead of counting products, this method stores the pairs themselves as keys in a hash table (tuple of indices). This allows for immediately identifying potential quadruples without checking every combination. The complexity remains O(n^2).
Here’s an example:
def find_quadruples(lst):
pairs = {}
count = 0
for i in range(len(lst)):
for j in range(i+1, len(lst)):
product = lst[i] * lst[j]
if product in pairs:
for pair in pairs[product]:
count += 1
pairs[product].append((i,j))
else:
pairs[product] = [(i,j)]
return count
example_list = [1, 6, 2, 6, 1]
print(find_quadruples(example_list))Output: 3
The code uses a dictionary to store index pairs that create the same product. Upon finding a matching product, it increases the count by the number of existing pairs and then adds the new pair to the dictionary.
Method 4: Sorting and Two Pointers
This method uses sorting and a two-pointer technique to identify pairs with the same product more efficiently. Pairs are sorted by their product, and quadruples are counted using pointers at both ends of the list, reducing the need for nested loops.
Here’s an example:
def find_quadruples(lst):
pairs = []
for i in range(len(lst) - 1):
for j in range(i+1, len(lst)):
pairs.append((lst[i]*lst[j], i, j))
pairs.sort()
count = 0
left = 0
right = left + 1
n = len(pairs)
while left < n:
while right < n and pairs[left][0] == pairs[right][0]:
if pairs[left][1] < pairs[right][1] and pairs[left][2] < pairs[right][1]:
count += 1
right += 1
left += 1
right = left + 1
return count
example_list = [1, 6, 2, 6, 1]
print(find_quadruples(example_list))Output: 3
This approach first constructs a list of all pairs as tuples (product, index1, index2). After sorting by product, it uses two pointers to identify matching products with non-overlapping index pairs, thereby finding quadruples.