Formatted question description: https://leetcode.ca/all/1726.html
1726. Tuple with Same Product
Level
Medium
Description
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) , (3,4,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 valids 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,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
Example 3:
Input: nums = [2,3,4,6,8,12]
Output: 40
Example 4:
Input: nums = [2,3,5,7]
Output: 0
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 10^4- All elements in
numsare distinct.
Solution
Loop over all pairs of elements in nums. For each pair of elements, calculate the two elements’ product. Use a hash map to store each product and the number of pairs (a, b) such that a * b equals the product.
Then loop over all entries of the map. For each product, if the number of pairs is count, then the number of tuples of the same product as the current product is count * (count - 1) * 4.
Finally, return the number of tuples.
class Solution {
public int tupleSameProduct(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int length = nums.length;
for (int i = 0; i < length; i++) {
int num1 = nums[i];
for (int j = i + 1; j < length; j++) {
int num2 = nums[j];
int product = num1 * num2;
int count = map.getOrDefault(product, 0) + 1;
map.put(product, count);
}
}
int tuples = 0;
Set<Integer> keySet = map.keySet();
for (int product : keySet) {
int count = map.get(product);
tuples += count * (count - 1) * 4;
}
return tuples;
}
}