We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Tuple with Same Product

Number: 1364

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given an array of distinct positive integers, the task is to count all valid tuples (a, b, c, d) such that a * b = c * d and a, b, c, and d are distinct elements from the array.

Key Insights

  • Every pair (a, b) forms a product, and we need to match it with a different pair (c, d) with the same product.
  • Use a hash table (or dictionary) to count the frequency of each product formed by pairs.
  • For each product value with count n, there are n choose 2 pairs of pairs, and each such pairing can form 8 different tuples due to ordering.
  • The overall number of tuples contributed by a product with frequency n is 8 * (n * (n - 1) / 2).

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of nums, because we iterate over all pairs. Space Complexity: O(n^2) in the worst-case scenario, to store the count of each product in the hash table.

Solution

The solution involves iterating over all unique pairs in the input array and computing their product. These products are stored in a hash map with their frequency. Once all pairs are processed, for every product with a frequency that is at least 2, we calculate the number of valid tuples by taking the combination of pairs (n choose 2) and multiply it by 8 (since for each two pairs, there are 8 different valid orderings of the four elements). This approach leverages counting and hash table data structures to ensure efficient computation.

Code Solutions

# Python solution for Tuple with Same Product
def tupleSameProduct(nums):
    # Dictionary to count frequency of products from all pairs
    product_count = {}
    
    n = len(nums)
    # Iterate over all unique pairs
    for i in range(n):
        for j in range(i + 1, n):
            prod = nums[i] * nums[j]
            if prod in product_count:
                product_count[prod] += 1
            else:
                product_count[prod] = 1
    
    count = 0
    # For each product, if there are at least 2 pairs, calculate valid tuples
    for prod in product_count:
        pairs = product_count[prod]
        if pairs > 1:
            # For each combination of two pairs, there are 8 valid tuples.
            count += 8 * (pairs * (pairs - 1) // 2)
    
    return count

# Example usage:
print(tupleSameProduct([2, 3, 4, 6]))   # Expected output: 8
print(tupleSameProduct([1, 2, 4, 5, 10]))  # Expected output: 16
← Back to All Questions