# Tuple with Same Product
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/tuple-with-same-product)
Canonical: https://scaleengineer.com/dsa/problems/tuple-with-same-product
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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**.

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible combinations of four distinct elements from the input array `nums` and checking if they satisfy the product condition. It is the most straightforward but also the least efficient method.
**Time:** O(n^4), where `n` is the number of elements in `nums`. This is due to the four nested loops required to check every possible ordered tuple of four distinct elements. · **Space:** O(1), as we only use a few variables to store the count and loop indices, not counting the input array.
**Pros:** Simple to understand and implement.; Requires no extra data structures, leading to constant space complexity.
**Cons:** Extremely inefficient with a time complexity of O(n^4).; Will not pass for larger inputs (e.g., n=1000) and will result in a 'Time Limit Exceeded' error.
### Explanation
The brute-force method directly translates the problem statement into code. We need to find the number of tuples `(a, b, c, d)` where the elements are distinct and `a * b = c * d`. We can achieve this by generating all possible ordered tuples of four distinct elements from the `nums` array and checking if the condition holds for each.

This is done using four nested loops to pick four indices `i, j, k, l`. Inside the loops, we must add checks to ensure that `i, j, k, l` are all unique. For each valid set of four distinct elements, we check if `nums[i] * nums[j] == nums[k] * nums[l]`. If they are equal, we increment a counter. Since the problem asks for tuples `(a, b, c, d)` where `a, b, c, d` are distinct elements, this direct check is sufficient. A crucial detail is to cast the products to a `long` type to avoid potential integer overflow, as the numbers can be up to 10<sup>4</sup>, and their product can exceed the capacity of a standard 32-bit integer.

```java
class Solution {
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        if (n < 4) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    for (int l = 0; l < n; l++) {
                        if (l == i || l == j || l == k) continue;
                        
                        if ((long)nums[i] * nums[j] == (long)nums[k] * nums[l]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Get the length of the array, `n`.
- Use four nested loops with indices `i`, `j`, `k`, `l` to iterate from `0` to `n-1`.
- Inside the innermost loop, ensure that all four indices are distinct from each other.
- Let `a = nums[i]`, `b = nums[j]`, `c = nums[k]`, `d = nums[l]`.
- Check if the product `a * b` equals `c * d`. Use a `long` cast to prevent integer overflow.
- If the products are equal, increment the `count`.
- After the loops complete, return the final `count`.

## Using a Hash Map to Count Products
A more efficient approach is to pre-calculate the products of all pairs of numbers and use a hash map to count the occurrences of each product. This transforms the problem from finding four numbers `(a, b, c, d)` to finding two pairs `(a, b)` and `(c, d)` that have the same product.
**Time:** O(n^2), where `n` is the number of elements. The dominant part is the nested loop to calculate products of all pairs, which takes O(n^2) time. Iterating through the map takes at most O(n^2) time as well. · **Space:** O(n^2), where `n` is the number of elements. In the worst-case scenario, every pair of numbers could result in a unique product, leading to `n * (n - 1) / 2` entries in the hash map.
**Pros:** Significantly more efficient than the brute-force approach.; Fast enough to pass the given constraints.; The logic is elegant, reducing a 4-element problem to a 2-pair problem.
**Cons:** Requires extra space for the hash map, which can be up to O(n^2) in the worst case.
### Explanation
The core idea is that the condition `a * b = c * d` implies that the pair `(a, b)` and the pair `(c, d)` share the same product. We can leverage this by first finding all pairs and grouping them by their product.

1.  **Count Pair Products**: We iterate through all unique pairs of distinct numbers from the `nums` array. For each pair `(nums[i], nums[j])` with `i < j`, we compute their product. We use a hash map, `productCounts`, to store the frequency of each product. The key is the product, and the value is the count of pairs that yield this product.

2.  **Calculate Tuples**: After populating the map, we iterate through it. If a product `p` has a frequency of `k` (meaning `k` pairs multiply to `p`), we can form tuples. To form a valid tuple `(a, b, c, d)`, we need to choose 2 distinct pairs from these `k` pairs. The number of ways to do this is given by the combination formula `C(k, 2) = k * (k - 1) / 2`.

3.  **Permutations**: For each combination of two pairs, say `{a, b}` and `{c, d}`, we can form 8 distinct valid tuples: `(a,b,c,d)`, `(a,b,d,c)`, `(b,a,c,d)`, `(b,a,d,c)`, and four more by swapping the positions of the two pairs. Thus, each combination of two pairs contributes 8 tuples.

The total number of tuples for a product with `k` pairs is `C(k, 2) * 8 = (k * (k - 1) / 2) * 8 = k * (k - 1) * 4`. We sum this value for all products with `k > 1` to get the final answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        if (n < 4) {
            return 0;
        }
        
        Map<Integer, Integer> productCounts = new HashMap<>();
        
        // Step 1: Find all pair products and their frequencies
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                productCounts.put(product, productCounts.getOrDefault(product, 0) + 1);
            }
        }
        
        int totalTuples = 0;
        
        // Step 2: Calculate the number of tuples
        for (int count : productCounts.values()) {
            if (count > 1) {
                // For 'count' pairs with the same product, we can choose 2 pairs in C(count, 2) ways.
                // C(count, 2) = count * (count - 1) / 2
                // Each pair of pairs gives 8 tuples.
                // Total tuples for this product = (count * (count - 1) / 2) * 8
                totalTuples += count * (count - 1) * 4;
            }
        }
        
        return totalTuples;
    }
}
```
### Algorithm
- Initialize a `HashMap` called `productCounts` to store products as keys and their frequencies as values.
- Initialize a result variable `totalTuples` to 0.
- Iterate through all unique pairs of numbers `(nums[i], nums[j])` where `i < j` using two nested loops.
- For each pair, calculate their product: `p = nums[i] * nums[j]`.
- Update the frequency of this product `p` in the `productCounts` map.
- After populating the map, iterate through the values (frequencies) in `productCounts`.
- For each frequency `k`, if `k > 1`, it means there are `k` pairs with the same product.
- The number of ways to choose 2 pairs from `k` is `C(k, 2) = k * (k - 1) / 2`.
- Each pair of pairs can form 8 valid tuples. So, add `C(k, 2) * 8` which simplifies to `k * (k - 1) * 4` to `totalTuples`.
- Return `totalTuples`.

# Solutions
### Java

```java
class Solution {
public
  int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int i = 1; i < nums.length; ++i) {
      for (int j = 0; j < i; ++j) {
        int x = nums[i] * nums[j];
        cnt.merge(x, 1, Integer : : sum);
      }
    }
    int ans = 0;
    for (int v : cnt.values()) {
      ans += v * (v - 1) / 2;
    }
    return ans << 3;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int tupleSameProduct(vector<int> &nums) {
    unordered_map<int, int> cnt;
    for (int i = 1; i < nums.size(); ++i) {
      for (int j = 0; j < i; ++j) {
        int x = nums[i] * nums[j];
        ++cnt[x];
      }
    }
    int ans = 0;
    for (auto &[_, v] : cnt) {
      ans += v * (v - 1) / 2;
    }
    return ans << 3;
  }
};

```

### Python

```python
class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int: cnt = defaultdict(int) for i in range(1, len(nums)): for j in range(i): x = nums[i] * nums[j] cnt[x] += 1 return sum(v * (v - 1) // 2 for v in cnt . values()) << 3

```