Tuple with Same Product

Medium
1142.

Tuple with Same Product

Tuple with Same Product is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

nums holds distinct positive integers. Count the ordered tuples (a, b, c, d) such that a * b == c * d, where a, b, c and d are elements of nums and all four are different (a != b != c != d, pairwise).

Tuples are ordered: (2, 6, 3, 4) and (6, 2, 3, 4) are counted separately.

Example 1

Input
nums = [1,2,3,6]
Output
8
Explanation
`1 * 6 = 2 * 3`, and that one match gives 8 orderings: `(1,6,2,3)`, `(1,6,3,2)`, `(6,1,2,3)`, `(6,1,3,2)`, `(2,3,1,6)`, `(3,2,1,6)`, `(2,3,6,1)`, `(3,2,6,1)`.

Example 2

Input
nums = [1,2,4,8,16]
Output
24
Explanation
`1*8 = 2*4`, `1*16 = 2*8` and `2*16 = 4*8` — three matches.

Example 3

Input
nums = [3,7]
Output
0

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
  • All elements in nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var tupleSameProduct = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Tuple with Same Product — Solution in Python, Java & C++

Tuple with Same Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Tuple with Same Product is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums holds distinct positive integers. Count the ordered tuples (a, b, c, d) such that a * b == c * d, where a, b, c and d are elements of nums and all four are different (a != b != c != d, pairwise).

Tuples are ordered: (2, 6, 3, 4) and (6, 2, 3, 4) are counted separately.

Example 1

Input: nums = [1,2,3,6]
Output: 8
Explanation: `1 * 6 = 2 * 3`, and that one match gives 8 orderings: `(1,6,2,3)`, `(1,6,3,2)`, `(6,1,2,3)`, `(6,1,3,2)`, `(2,3,1,6)`, `(3,2,1,6)`, `(2,3,6,1)`, `(3,2,6,1)`.

Example 2

Input: nums = [1,2,4,8,16]
Output: 24
Explanation: `1*8 = 2*4`, `1*16 = 2*8` and `2*16 = 4*8` — three matches.

Example 3

Input: nums = [3,7]
Output: 0

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
  • All elements in nums are distinct.

Hints for Tuple with Same Product

  1. Hint 1

    Think in terms of unordered pairs {a, b} and their products.

  2. Hint 2

    Two different pairs with the same product never share an element (the values are distinct), so any two of them form valid tuples.

  3. Hint 3

    Count how many pairs give each product. A product shared by c pairs contributes C(c, 2) matches, and each match yields 8 ordered tuples.

How to solve Tuple with Same Product

Group the n(n-1)/2 pairs by product; every two pairs in one group make 8 ordered tuples.

Approach

  1. For every i < j, increment count[nums[i] * nums[j]].
  2. For each product with c pairs, add 8 * c * (c - 1) / 2, i.e. 4 * c * (c - 1).
  3. Return the sum.

Why it works

If {a, b} != {c, d} and a * b == c * d with distinct values, the pairs are disjoint: sharing a = c would force b = d. So each unordered pair of pairs is a valid match, and its tuples come from ordering within each pair (2 · 2) and choosing which pair goes first (2): 8 in total.

Complexity

  • Time — O(n^2)
  • Space — O(n^2)

Pitfalls

  • Counting ordered pairs instead of unordered ones overcounts by a factor of 4.
  • The distinctness of the values is what makes every match valid — without it you would need to exclude shared elements.
  • Products reach 10^8, which still fits in a 32-bit integer.

Reference solution

Python

from typing import List

def tupleSameProduct(nums: List[int]) -> int:
    count = {}
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            p = nums[i] * nums[j]
            count[p] = count.get(p, 0) + 1
    return sum(4 * c * (c - 1) for c in count.values())

Java

public static int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            count.merge(nums[i] * nums[j], 1, Integer::sum);
        }
    }
    int total = 0;
    for (int c : count.values()) total += 4 * c * (c - 1);
    return total;
}

C++

int tupleSameProduct(vector<int>& nums) {
    unordered_map<int, int> count;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) count[nums[i] * nums[j]]++;
    }
    int total = 0;
    for (auto& kv : count) total += 4 * kv.second * (kv.second - 1);
    return total;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets