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:
Another example:
If nums = [1,2,4,5,10]
, the expected output is 16 because:
Clarifications:
nums
is between 1 and 1000, i.e. 1 <= nums.length <= 1000
.nums
is a positive integer between 1 and 10000, i.e. 1 <= nums[i] <= 10^4
.nums
are distinct.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
O(n^4), where n is the number of elements in the input array nums
.
O(1), as we are only using a constant amount of extra space.
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
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.
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.
nums
are distinct, so we don't need to handle this edge case.