Tuple with Same Product

medium hashing counting combinatorics

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, d are elements of nums and a, b, c, d are all different positions.

Inputnums = [2,3,4,6]

Output8

Only one product repeats: 2·6 = 3·4 = 12. Those two equal pairs can be arranged into 8 valid tuples.

Inputnums = [1,2,4,5,10]

Output16

Two products repeat: 1·10 = 2·5 = 10 and 2·10 = 4·5 = 20, each giving 8 tuples.

nums (distinct positive integers, comma-separated)

def tuple_same_product(nums):
    count = {}
    total = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            p = nums[i] * nums[j]
            total += 8 * count.get(p, 0)
            count[p] = count.get(p, 0) + 1
    return total

function tupleSameProduct(nums) {
  const count = new Map();
  let total = 0;
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const p = nums[i] * nums[j];
      total += 8 * (count.get(p) || 0);
      count.set(p, (count.get(p) || 0) + 1);
    }
  }
  return total;
}

int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    int total = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int p = nums[i] * nums[j];
            total += 8 * count.getOrDefault(p, 0);
            count.merge(p, 1, Integer::sum);
        }
    }
    return total;
}

int tupleSameProduct(vector<int>& nums) {
    unordered_map<int, int> count;
    int total = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int p = nums[i] * nums[j];
            total += 8 * count[p];
            count[p]++;
        }
    }
    return total;
}

Explanation

The key observation is that a valid tuple (a, b, c, d) with a·b = c·d is really two different pairs that share the same product. So the whole problem reduces to: how many unordered pairs of distinct elements collide on the same product?

We hash every pairwise product. Iterate over all i < j, compute p = nums[i]·nums[j], and keep a map count[p] of how many earlier pairs already produced p.

When we meet a new pair with product p that already has count[p] earlier pairs, this pair can combine with each of those earlier pairs. Each such combination of two pairs {a,b} and {c,d} yields 8 ordered tuples: the first pair has 2 internal orders, the second pair has 2 internal orders, and the two pairs can swap roles (×2), so 2·2·2 = 8. We therefore add 8 · count[p] before incrementing count[p].

Equivalently, if a product appears in k pairs total, it contributes 8·C(k,2) = 4·k·(k−1) tuples. Adding 8·count[p] on each new pair telescopes to exactly that sum.

Example: [2,3,4,6]. The products are 6, 8, 12, 12, 18, 24. Only 12 repeats (from 2·6 and 3·4), so when the second pair lands we add 8·1 = 8. The answer is 8.

Time: O(n²) Space: O(n²)