Today’s problem

https://leetcode.com/problems/tuple-with-same-product/description/

Intuition

In this question, all we need to do is to find the tuple that the numbers in the tuple has the same multiplication value. For example, if there are n pairs of numbers that has the same multiplication value, then the result would be $(^2_n) \times 4$. This is because we can pick any two pair from the set and form a tuple.

The question was, why can you prove that this two pairs are distinct?

This is because the original array is distinct. This means that there are no duplicated numbers in the original array. Therefore, if $a \times b = c \times d$, we know that $a \ne c$, then we can now that $b \ne d$.

Approach

Therefore, all we need to do is to iterate through the whole list and find all tuples that has the same multiplication.

Trick

Among four dictionaries, defaultdict, Counter, dict, and {}, dict has the fastest speed.

Complexity

• Time complexity: $O(N ^ 2)$, N is the length of the array.

• Space complexity: $O(N)$, we need to store the whole array.

Code

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        nums.sort()
        cnt = dict()
        N = len(nums)
        for i in range(N):
            for j in range(i + 1, N):
                tmp = nums[i] * nums[j]
                if tmp not in cnt:
                    cnt[tmp] = 1
                else:
                    cnt[tmp] += 1        
        ans = 0
        for v in cnt.values():
            ans += 4 * (v) * (v - 1)
        
        return ans