Tuple with Same Product — Product Frequency Map

Problem 188 · Tuple with Same Product

Difficulty: Medium · Pattern: Product Frequency Map

Count tuples (a,b,c,d) from nums where ab = cd (all distinct indices).

Intuition

For every pair (i,j), record their product in a map. If a product has been seen k times before, it forms k new pairs → each pair of pairs gives 8 tuples (permutations).

Solutions

// C++
int tupleSameProduct(vector<int>& nums) {
    unordered_map<int,int> cnt;
    int n = nums.size(), ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int prod = nums[i]*nums[j];
            ans += 8 * cnt[prod];
            cnt[prod]++;
        }
    return ans;
}

// Java
public int tupleSameProduct(int[] nums) {
    Map<Integer,Integer> cnt = new HashMap<>();
    int n = nums.length, ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int prod = nums[i]*nums[j];
            ans += 8 * cnt.getOrDefault(prod, 0);
            cnt.merge(prod, 1, Integer::sum);
        }
    return ans;
}

# Python
from collections import defaultdict
def tupleSameProduct(nums):
    cnt = defaultdict(int)
    ans = 0
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            prod = nums[i]*nums[j]
            ans += 8 * cnt[prod]
            cnt[prod] += 1
    return ans

Complexity

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