Tuple with Same Product
MedPrompt
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 <= 10001 <= nums[i] <= 104- All elements in
numsare 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
countto 0. - Get the length of the array,
n. - Use four nested loops with indices
i,j,k,lto iterate from0ton-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 * bequalsc * d. Use alongcast 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.
class Solution { public int tupleSameProduct(int[] nums) { int n = nums.length; if (n < 4) { return 0; } int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; for (int l = 0; l < n; l++) { if (l == i || l == j || l == k) continue; if ((long)nums[i] * nums[j] == (long)nums[k] * nums[l]) { count++; } } } } } return count; }}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.
Solutions
Solution
class Solution {public int tupleSameProduct(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); for (int i = 1; i < nums.length; ++i) { for (int j = 0; j < i; ++j) { int x = nums[i] * nums[j]; cnt.merge(x, 1, Integer : : sum); } } int ans = 0; for (int v : cnt.values()) { ans += v * (v - 1) / 2; } return ans << 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.