Tuple with Same Product

Med

#1582Time: O(n^4), where `n` is the number of elements in `nums`. This is due to the four nested loops required to check every possible ordered tuple of four distinct elements.Space: O(1), as we only use a few variables to store the count and loop indices, not counting the input array.

Patterns

Counting

Data structures

Array Hash Table

Prompt

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, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through all possible combinations of four distinct elements from the input array nums and checking if they satisfy the product condition. It is the most straightforward but also the least efficient method.

Algorithm

Initialize a counter count to 0.
Get the length of the array, n.
Use four nested loops with indices i, j, k, l to iterate from 0 to n-1.
Inside the innermost loop, ensure that all four indices are distinct from each other.
Let a = nums[i], b = nums[j], c = nums[k], d = nums[l].
Check if the product a * b equals c * d. Use a long cast to prevent integer overflow.
If the products are equal, increment the count.
After the loops complete, return the final count.

Walkthrough

The brute-force method directly translates the problem statement into code. We need to find the number of tuples (a, b, c, d) where the elements are distinct and a * b = c * d. We can achieve this by generating all possible ordered tuples of four distinct elements from the nums array and checking if the condition holds for each.

This is done using four nested loops to pick four indices i, j, k, l. Inside the loops, we must add checks to ensure that i, j, k, l are all unique. For each valid set of four distinct elements, we check if nums[i] * nums[j] == nums[k] * nums[l]. If they are equal, we increment a counter. Since the problem asks for tuples (a, b, c, d) where a, b, c, d are distinct elements, this direct check is sufficient. A crucial detail is to cast the products to a long type to avoid potential integer overflow, as the numbers can be up to 10<sup>4</sup>, and their product can exceed the capacity of a standard 32-bit integer.

1class Solution {2    public int tupleSameProduct(int[] nums) {3        int n = nums.length;4        if (n < 4) {5            return 0;6        }7        int count = 0;8        for (int i = 0; i < n; i++) {9            for (int j = 0; j < n; j++) {10                if (i == j) continue;11                for (int k = 0; k < n; k++) {12                    if (k == i || k == j) continue;13                    for (int l = 0; l < n; l++) {14                        if (l == i || l == j || l == k) continue;15                        16                        if ((long)nums[i] * nums[j] == (long)nums[k] * nums[l]) {17                            count++;18                        }19                    }20                }21            }22        }23        return count;24    }25}

Complexity

Time

O(n^4), where `n` is the number of elements in `nums`. This is due to the four nested loops required to check every possible ordered tuple of four distinct elements.

Space

O(1), as we only use a few variables to store the count and loop indices, not counting the input array.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra data structures, leading to constant space complexity.

Cons

Extremely inefficient with a time complexity of O(n^4).
Will not pass for larger inputs (e.g., n=1000) and will result in a 'Time Limit Exceeded' error.

A more efficient approach is to pre-calculate the products of all pairs of numbers and use a hash map to count the occurrences of each product. This transforms the problem from finding four numbers (a, b, c, d) to finding two pairs (a, b) and (c, d) that have the same product.

Algorithm

Initialize a HashMap called productCounts to store products as keys and their frequencies as values.
Initialize a result variable totalTuples to 0.
Iterate through all unique pairs of numbers (nums[i], nums[j]) where i < j using two nested loops.
For each pair, calculate their product: p = nums[i] * nums[j].
Update the frequency of this product p in the productCounts map.
After populating the map, iterate through the values (frequencies) in productCounts.
For each frequency k, if k > 1, it means there are k pairs with the same product.
The number of ways to choose 2 pairs from k is C(k, 2) = k * (k - 1) / 2.
Each pair of pairs can form 8 valid tuples. So, add C(k, 2) * 8 which simplifies to k * (k - 1) * 4 to totalTuples.
Return totalTuples.

Walkthrough

The core idea is that the condition a * b = c * d implies that the pair (a, b) and the pair (c, d) share the same product. We can leverage this by first finding all pairs and grouping them by their product.

Count Pair Products: We iterate through all unique pairs of distinct numbers from the nums array. For each pair (nums[i], nums[j]) with i < j, we compute their product. We use a hash map, productCounts, to store the frequency of each product. The key is the product, and the value is the count of pairs that yield this product.
Calculate Tuples: After populating the map, we iterate through it. If a product p has a frequency of k (meaning k pairs multiply to p), we can form tuples. To form a valid tuple (a, b, c, d), we need to choose 2 distinct pairs from these k pairs. The number of ways to do this is given by the combination formula C(k, 2) = k * (k - 1) / 2.
Permutations: For each combination of two pairs, say {a, b} and {c, d}, we can form 8 distinct valid tuples: (a,b,c,d), (a,b,d,c), (b,a,c,d), (b,a,d,c), and four more by swapping the positions of the two pairs. Thus, each combination of two pairs contributes 8 tuples.

The total number of tuples for a product with k pairs is C(k, 2) * 8 = (k * (k - 1) / 2) * 8 = k * (k - 1) * 4. We sum this value for all products with k > 1 to get the final answer.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int tupleSameProduct(int[] nums) {6        int n = nums.length;7        if (n < 4) {8            return 0;9        }10        11        Map<Integer, Integer> productCounts = new HashMap<>();12        13        // Step 1: Find all pair products and their frequencies14        for (int i = 0; i < n; i++) {15            for (int j = i + 1; j < n; j++) {16                int product = nums[i] * nums[j];17                productCounts.put(product, productCounts.getOrDefault(product, 0) + 1);18            }19        }20        21        int totalTuples = 0;22        23        // Step 2: Calculate the number of tuples24        for (int count : productCounts.values()) {25            if (count > 1) {26                // For 'count' pairs with the same product, we can choose 2 pairs in C(count, 2) ways.27                // C(count, 2) = count * (count - 1) / 228                // Each pair of pairs gives 8 tuples.29                // Total tuples for this product = (count * (count - 1) / 2) * 830                totalTuples += count * (count - 1) * 4;31            }32        }33        34        return totalTuples;35    }36}

Complexity

Time

O(n^2), where `n` is the number of elements. The dominant part is the nested loop to calculate products of all pairs, which takes O(n^2) time. Iterating through the map takes at most O(n^2) time as well.

Space

O(n^2), where `n` is the number of elements. In the worst-case scenario, every pair of numbers could result in a unique product, leading to `n * (n - 1) / 2` entries in the hash map.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Fast enough to pass the given constraints.
The logic is elegant, reducing a 4-element problem to a 2-pair problem.

Cons

Requires extra space for the hash map, which can be up to O(n^2) in the worst case.

Solutions

Solution

1class Solution {2public3  int tupleSameProduct(int[] nums) {4    Map<Integer, Integer> cnt = new HashMap<>();5    for (int i = 1; i < nums.length; ++i) {6      for (int j = 0; j < i; ++j) {7        int x = nums[i] * nums[j];8        cnt.merge(x, 1, Integer : : sum);9      }10    }11    int ans = 0;12    for (int v : cnt.values()) {13      ans += v * (v - 1) / 2;14    }15    return ans << 3;16  }17}

1class Solution {2public:3  int tupleSameProduct(vector<int> &nums) {4    unordered_map<int, int> cnt;5    for (int i = 1; i < nums.size(); ++i) {6      for (int j = 0; j < i; ++j) {7        int x = nums[i] * nums[j];8        ++cnt[x];9      }10    }11    int ans = 0;12    for (auto &[_, v] : cnt) {13      ans += v * (v - 1) / 2;14    }15    return ans << 3;16  }17};

1class Solution:2    def tupleSameProduct(self, nums: List[int]) -> int: cnt = defaultdict(int) for i in range(1, len(nums)): for j in range(i): x = nums[i] * nums[j] cnt[x] += 1 return sum(v * (v - 1) // 2 for v in cnt . values()) << 3

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem