Taro Logo

Tuple with Same Product

Medium
Google logo
Google
1 view
Topics:
Arrays

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.

For example:

Consider nums = [2,3,4,6]. The expected output is 8 because the following tuples satisfy the condition:

  • (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)

Another example:

If nums = [1,2,4,5,10], the expected output is 16 because:

  • (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)

Clarifications:

  • The length of nums is between 1 and 1000, i.e. 1 <= nums.length <= 1000.
  • Each element in nums is a positive integer between 1 and 10000, i.e. 1 <= nums[i] <= 10^4.
  • All elements in nums are distinct.

Solution


Brute Force Solution

A naive approach would be to iterate through all possible combinations of (a, b, c, d) from the input array nums and check if a * b == c * d. We also need to ensure that a, b, c, and d are distinct elements.

def count_tuples_brute_force(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            for k in range(n):
                if k == i or k == j:
                    continue
                for l in range(n):
                    if l == i or l == j or l == k:
                        continue
                    if nums[i] * nums[j] == nums[k] * nums[l]:
                        count += 1
    return count

Time Complexity

O(n^4), where n is the number of elements in the input array nums.

Space Complexity

O(1), as we are only using a constant amount of extra space.

Optimal Solution

We can optimize the solution by using a hash map to store the product of pairs of numbers and their frequency. First, iterate through all possible pairs (a, b) and store the product a * b as a key in the hash map, with the value being the number of times that product occurs. Then, iterate through the hash map and for each product, calculate the number of tuples that can be formed from the frequency of that product. Since the order matters (a,b,c,d) is different from (b,a,c,d), for each product we use count * (count - 1) as we need two pairs with the same product and order matters

from collections import defaultdict

def count_tuples(nums):
    count = 0
    product_map = defaultdict(int)
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if i != j:
                product_map[nums[i] * nums[j]] += 1

    for product, freq in product_map.items():
        count += freq * (freq - 1)

    return count

Time Complexity

O(n^2), where n is the number of elements in the input array nums. This is because we iterate through all possible pairs of numbers.

Space Complexity

O(n^2) in the worst case, as the hash map product_map can store up to n^2 different products if all products are unique.

Edge Cases

  • Empty input array: If the input array is empty, the function should return 0.
  • Input array with one element: If the input array has only one element, it's not possible to form tuples, so the function should return 0.
  • Input array with duplicate numbers: The problem states that all elements in nums are distinct, so we don't need to handle this edge case.
  • Large products: Be mindful of potential integer overflow issues if the products of the numbers become very large. Python handles large integers automatically, but in other languages, you might need to use appropriate data types or consider using modular arithmetic if the problem specifies a modulo.