1726. Tuple with Same Product

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.

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

Example 3:

Input: nums = [2,3,4,6,8,12]
Output: 40

Example 4:

Input: nums = [2,3,5,7]
Output: 0

Constraints:

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

Solution

Loop over all pairs of elements in nums. For each pair of elements, calculate the two elements’ product. Use a hash map to store each product and the number of pairs (a, b) such that a * b equals the product.

Then loop over all entries of the map. For each product, if the number of pairs is count, then the number of tuples of the same product as the current product is count * (count - 1) * 4.

Finally, return the number of tuples.

JAVA

• class Solution {
      public int tupleSameProduct(int[] nums) {
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          int length = nums.length;
          for (int i = 0; i < length; i++) {
              int num1 = nums[i];
              for (int j = i + 1; j < length; j++) {
                  int num2 = nums[j];
                  int product = num1 * num2;
                  int count = map.getOrDefault(product, 0) + 1;
                  map.put(product, count);
              }
          }
          int tuples = 0;
          Set<Integer> keySet = map.keySet();
          for (int product : keySet) {
              int count = map.get(product);
              tuples += count * (count - 1) * 4;
          }
          return tuples;
      }
  }
  
  ############
  
  class Solution {
      public int tupleSameProduct(int[] nums) {
          Map<Integer, Integer> cnt = new HashMap<>();
          for (int i = 1; i < nums.length; ++i) {
              for (int j = 0; j < i; ++j) {
                  int x = nums[i] * nums[j];
                  cnt.put(x, cnt.getOrDefault(x, 0) + 1);
              }
          }
          int ans = 0;
          for (int v : cnt.values()) {
              ans += v * (v - 1) / 2;
          }
          return ans << 3;
      }
  }

C++

• class Solution {
  public:
      int tupleSameProduct(vector<int>& nums) {
          unordered_map<int, int> cnt;
          for (int i = 1; i < nums.size(); ++i) {
              for (int j = 0; j < i; ++j) {
                  int x = nums[i] * nums[j];
                  ++cnt[x];
              }
          }
          int ans = 0;
          for (auto& [_, v] : cnt) {
              ans += v * (v - 1) / 2;
          }
          return ans << 3;
      }
  };

PYTHON

from collections import defaultdict

class Solution:
    def tupleSameProduct(self, nums):
        product_count = defaultdict(int)
        
        # Compute all product pairs
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                product = nums[i] * nums[j]
                product_count[product] += 1  # Count occurrences
        
        # Calculate valid tuples
        tuples = sum(count * (count - 1) * 4 for count in product_count.values())
        return tuples