Welcome to Subscribe On Youtube

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 <= 1000
  • 1 <= nums[i] <= 10^4
  • All elements in nums are 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;
    }
}

  • Todo

  • class Solution:
    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

############

# 1726. Tuple with Same Product
# https://leetcode.com/problems/tuple-with-same-product/

class Solution:
    def tupleSameProduct(self, nums: List[int]):
        res = 0
        n = len(nums)
        s = Counter()
        
        for a in range(n):
            for b in range(a+1,n):
                t = nums[a] * nums[b]
                res += s[t]
                s[t] += 1

        return 8 * res

All Problems

All Solutions