Problem

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.

Examples

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) , (4,3,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 valid 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,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • All elements in nums are distinct.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

The naive solution for this problem would involve iterating over all possible quadruplets (a, b, c, d) and checking if they satisfy the condition a * b = c * d. This can be achieved using four nested loops.

Approach:

  1. Iterate Over All Quadruplets:
    • Use four nested loops to iterate over every combination of a, b, c, and d in the array nums.
  2. Check the Product Condition:
    • For each quadruplet (a, b, c, d), check if a * b is equal to c * d.
  3. Ensure Distinct Elements:
    • Ensure that all four elements a, b, c, and d are distinct.
  4. Count Valid Quadruplets:
    • Count the number of valid quadruplets that satisfy the conditions.

Code

Java
class Solution {
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        int res = 0;

        // Iterate over all quadruplets
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    for (int l = k + 1; l < n; l++) {
                        if (l == i || l == j) continue;
                        if (nums[i] * nums[j] == nums[k] * nums[l]) {
                            res++;
                        }
                    }
                }
            }
        }

        return res * 8; // Each valid quadruplet has 8 permutations
    }
}
Python
class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        # Iterate over all quadruplets
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(n):
                    if k == i or k == j:
                        continue
                    for l in range(k + 1, n):
                        if l == i or l == j:
                            continue
                        if nums[i] * nums[j] == nums[k] * nums[l]:
                            res += 1

        return res * 8  # Each valid quadruplet has 8 permutations

Complexity

  • ⏰ Time complexity: O(n^4) because there are four nested loops each iterating over n elements.
  • 🧺 Space complexity: O(1) because we are not using any extra space proportional to the input size.

Method 2 - Using Frequency Map

Given distinct positive integers in the array nums, we need to find tuples (a, b, c, d) such that a * b = c * d and a != b != c != d.

We can utilize a HashMap (or dictionary in Python) to store the product of pairs and the list of indices that create that product.

Here is the approach:

  • Iterate over all pairs of elements in the array.
  • Calculate the product of each pair and store it in a HashMap along with the pairs’ indices.
  • Check if the product has already been seen. If yes, count how many valid tuples can be formed.

Code

Java
class Solution {
    public int tupleSameProduct(int[] nums) {
        Map<Integer, Integer> productMap = new HashMap<>();
		int n = nums.length;
        // Iterate over all pairs and store the count of each product
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                productMap.put(product, productMap.getOrDefault(product, 0) + 1);
            }
        }

        // Count the number of valid tuples
        int ans = 0;
        for (int count : productMap.values()) {
            if (count > 1) {
                ans += (count * (count - 1)) / 2; // number of tuples that can be formed
            }
        }

        return ans * 8; // each tuple has 8 permutations
    }
}
Python
class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        n: int = len(nums)
        product_map: dict[int, int] = defaultdict(int)
        res: int = 0

        # Iterate over all pairs and store the count of each product
        for i in range(n):
            for j in range(i + 1, n):
                product = nums[i] * nums[j]
                product_map[product] += 1

        # Count the number of valid tuples
        for count in product_map.values():
            if count > 1:
                res += (count * (count - 1)) // 2  # number of tuples that can be formed

        return res * 8  # each tuple has 8 permutations

Complexity

  • ⏰ Time complexity: O(n^2) where n is the length of the array because we iterate through all pairs.
  • 🧺 Space complexity: O(n^2) in the worst case if all pairs have unique products, but generally lower since it’s based on the number of unique products.