1726. Tuple with Same Product

Time: O(n²)

Space: O(n²)

Intuition

Count tuples (i,j,k,l) where nums[i]*nums[j]==nums[k]*nums[l]. For each product value, count pairs with that product. Tuples = C(count,2)*8 for distinct indices.

Algorithm

1Map product -> count of pairs with that product.
2For each pair (i,j): product = nums[i]*nums[j]. tuples += map[product]. Map[product]++.

Common Pitfalls

•Each pair of pairs gives 8 tuples (reordering the two pairs and swapping within pairs). Multiply by 8.

1726.cs

// Approach: Count all pairwise products in a HashMap; each duplicate pair yields 8 tuples.
// Time: O(n²) Space: O(n²)

public class Solution
{
    public int TupleSameProduct(int[] nums)
    {
        int ans = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                int prod = nums[i] * nums[j];
                ans += count.GetValueOrDefault(prod, 0) * 8;
                if (count.ContainsKey(prod))
                    count[prod]++;
                else
                    count[prod] = 1;
            }
        }

        return ans;
    }
}

Was this solution helpful?