1726. Tuple with Same Product

[mah-shamim]

Topics: Array, Hash Table, Counting

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

• Input: nums = [2,3,4,6]
• Output: 8
• Explanation: There are 8 valid tuples:
  (2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
  (3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

• Input: nums = [1,2,4,5,10]
• Output: 16
• Explanation: There are 16 valid tuples:
  (1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
  (2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
  (2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
  (4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• All elements in nums are distinct.

Hint:

1. Note that all of the integers are distinct. This means that each time a product is formed it must be formed by two unique integers.
2. Count the frequency of each product of 2 distinct numbers. Then calculate the permutations formed.

[mah-shamim]

We need to determine the number of valid tuples (a, b, c, d) from a given array of distinct positive integers such that the product of a and b is equal to the product of c and d, with all four elements being distinct.

Approach

1. Generate Products of Pairs: Compute the product of all possible pairs of distinct elements in the array. This helps us identify which products can be formed by different pairs of elements.
2. Count Product Frequencies: Use a hash map to count how many times each product appears. Each key in the hash map is a product, and the value is the number of distinct pairs that produce this product.
3. Calculate Valid Tuples: For each product that can be formed by at least two different pairs, calculate the number of valid tuples. The formula used here is derived from combinatorial permutations, considering the different ways pairs can be ordered and combined.

Let's implement this solution in PHP: 1726. Tuple with Same Product

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function tupleSameProduct($nums) {
    $productCounts = array();
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            $prod = $nums[$i] * $nums[$j];
            if (isset($productCounts[$prod])) {
                $productCounts[$prod]++;
            } else {
                $productCounts[$prod] = 1;
            }
        }
    }
    $total = 0;
    foreach ($productCounts as $count) {
        if ($count >= 2) {
            $total += 4 * $count * ($count - 1);
        }
    }
    return $total;
}

// Example 1
$nums1 = [2, 3, 4, 6];
echo "Output: " . tupleSameProduct($nums1) . "\n"; // Output: 8

// Example 2
$nums2 = [1, 2, 4, 5, 10];
echo "Output: " . tupleSameProduct($nums2) . "\n"; // Output: 16
?>

Explanation:

1. Generate Products of Pairs: We iterate over all possible pairs of elements (i, j) where i < j to ensure each pair is considered only once. For each pair, we compute their product and store the count of each product in a hash map.
2. Count Product Frequencies: The hash map keeps track of how many distinct pairs result in the same product. This helps us quickly determine which products can form valid tuples.
3. Calculate Valid Tuples: For each product that appears at least twice, we use the formula 4 × k × (k - 1) where k is the count of pairs for that product. This formula accounts for all permutations of the pairs (a, b) and (c, d), considering both the order of elements within each pair and the order of the pairs themselves.

This approach efficiently counts all valid tuples by leveraging combinatorial counting and hash maps to track product frequencies, ensuring an optimal solution within the problem

[kovatz]

Thanks for solving the problem of "Tuple with Same Product"

[mah-shamim]

Thanks