⚡Flashcard Drill➔
NeetCode #930LC-1726MediumMath & Geometry
← Back to All Problems

#930 · #1726 · Tuple with Same Product(同积元组)

📌 Problem Statement & Constraints

Given an array nums of distinct positive integers, count the tuples (a, b, c, d) with a * b = c * d where a, b, c, d are four distinct elements of nums in any order. Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 10^4, all elements distinct.

💡 Core Algorithmic Approaches

  1. Enumerate every unordered pair and count how many pairs share each product using a hash map.
  2. If a product occurs k times, any two of those pairs form a valid set of four indices, giving C(k, 2) index-quadruples.
  3. Because the elements are distinct, two different pairs never share an index, so no extra filtering is needed.
  4. Each index-quadruple yields 8 ordered tuples (a, b, c, d): 2 ways to order the two pairs times 2 orderings inside each pair. Answer = sum(C(k, 2) * 8).

💻 Benchmark Python3 Implementation

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        from collections import defaultdict
        from itertools import combinations
        cnt = defaultdict(int)
        for a, b in combinations(nums, 2):
            cnt[a * b] += 1
        res = 0
        for k in cnt.values():
            res += k * (k - 1) // 2 * 8      # C(k, 2) pairs of pairs, 8 orders each
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): all pairs are enumerated.
💾 Space Complexity
O(n^2): the product hash map.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the factor 8: each choice of two pairs gives 8 ordered tuples, not 4 — 2 pair orderings times 2 internal orderings per pair.
  • Brute-forcing four nested loops: O(n^4) with n = 1000 is far too slow.
  • Fearing repeated indices: the distinctness guarantee means any two distinct pairs use four different indices.
  • Using a set of products instead of counts: the multiplicity is needed to apply C(k, 2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems