1726. Tuple with Same Product

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/tuple-with-same-product
• topics: Hash Table

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.

Idea

• Use counter and multiply by $8\times (n-1)$

Code

class Solution:
    def tupleSameProduct(self, nums):
        product_count = defaultdict(int)
        ans = 0
 
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                product = nums[i] * nums[j]
                ans += 8 * product_count[product]
                product_count[product] += 1
 
        return ans