Count Pairs Whose Products Exist in Array

Table of Contents#

1. Problem Statement
2. Brute - Force Approach
   • Explanation
   • Complexity Analysis
   • Example Code
3. Using Hashing (Optimal Approach)
   • Explanation
   • Complexity Analysis
   • Example Code
4. Common Practices
   • Input Validation
   • Handling Edge Cases
5. Best Practices
   • Choosing the Right Data Structure
   • Code Optimization
6. Example Usage in Different Scenarios
   • Small Arrays
   • Large Arrays
7. Conclusion
8. References

1. Problem Statement#

Given an array arr of integers, we need to count the number of unordered pairs (i, j) such that i < j and arr[i] * arr[j] is also an element of the array.

2. Brute - Force Approach#

Explanation#

The brute - force approach involves checking every possible pair of elements in the array. For each pair (i, j) where i < j, we calculate the product arr[i] * arr[j] and then check if this product exists in the array.

Complexity Analysis#

• Time Complexity: The time complexity of this approach is $O(n^2)$ because we have two nested loops to check all pairs of elements. The inner loop for checking if the product exists in the array has a time complexity of $O(n)$ in the worst case (if we use a linear search). So, overall, it is $O(n^3)$ if we use linear search for checking the product. If we use a sorted array and binary search for checking the product, the time complexity for checking the product is $O(\log n)$, making the overall time complexity $O(n^2\log n)$.
• Space Complexity: The space complexity is $O(1)$ (assuming no extra space is used other than a few variables for counting and looping).

Example Code (using linear search for checking product)#

def count_pairs_brute_force(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            product = arr[i] * arr[j]
            found = False
            for k in range(n):
                if arr[k] == product:
                    found = True
                    break
            if found:
                count += 1
    return count

3. Using Hashing (Optimal Approach)#

Explanation#

We can use a hash set (or a dictionary in some languages) to store the elements of the array. This allows us to check if the product of a pair exists in the array in $O(1)$ average time. First, we create a hash set from the array elements. Then, we iterate through all pairs of elements, calculate their product, and check if the product is in the hash set.

Complexity Analysis#

• Time Complexity: The time complexity of creating the hash set is $O(n)$. The two nested loops for checking pairs have a time complexity of $O(n^2)$. And the check for the product in the hash set is $O(1)$ on average. So, the overall time complexity is $O(n^2)$.
• Space Complexity: The space complexity is $O(n)$ because we are using a hash set to store the elements of the array.

Example Code (using Python's set)#

def count_pairs_hash(arr):
    count = 0
    hash_set = set(arr)
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            product = arr[i] * arr[j]
            if product in hash_set:
                count += 1
    return count

4. Common Practices#

Input Validation#

• Always check if the input array is empty. If it is, the result is obviously 0.
• Check the data type of the elements in the array. If the array is supposed to contain integers (as in our problem statement), make sure there are no non - integer elements.

Handling Edge Cases#

• Zero in the array: If the array contains zero, pairs with zero may or may not contribute to the count depending on the problem's exact requirements. For example, if the array is [0, 0, 0], the product of any pair is zero, which is in the array.
• Negative numbers: When dealing with negative numbers, the product can be positive or negative. Make sure the hash set (or other data structures) can handle negative values correctly.

5. Best Practices#

Choosing the Right Data Structure#

• As we saw, using a hash set (or a hash map in languages like Java) is much more efficient than using linear search for checking if the product exists. In Python, the set data structure provides an average $O(1)$ time complexity for membership checks.
• If memory is a concern and the array elements are in a known range (e.g., small integers), we could use a boolean array (like a frequency array) instead of a hash set.

Code Optimization#

• Avoid redundant calculations: For example, if the array has duplicate elements, we can skip some pairs. But this requires careful handling to avoid under - counting or over - counting.
• Pre - processing: If the array is very large, we could consider parallelizing the pair - checking process (in languages that support parallel programming).

6. Example Usage in Different Scenarios#

Small Arrays#

arr_small = [1, 2, 3, 6]
print(count_pairs_hash(arr_small))

In this case, the pairs (1, 6) (product 6), (2, 3) (product 6) are counted. The output is 2.

Large Arrays#

import random
arr_large = [random.randint(1, 1000) for _ in range(1000)]
print(count_pairs_hash(arr_large))

Here, we generate a large array of 1000 random integers. The hashing approach will still work efficiently, while the brute - force approach (especially with linear search) will be very slow.

7. Conclusion#

Counting pairs whose products exist in an array can be solved using different algorithms. The brute - force approach is simple but not efficient for large arrays. The hashing approach is much more optimal in terms of time complexity. By following common and best practices like input validation, handling edge cases, and choosing the right data structure, we can write clean and efficient code to solve this problem.

8. References#

• [Python Documentation on Sets](https://docs.python.org/3/library/stdtypes.html#set - types - set - frozenset)
• Introduction to Algorithms (CLRS)