Skip to content

1726. Tuple with Same Product 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  int tupleSameProduct(vector<int>& nums) {
    int ans = 0;
    unordered_map<int, int> count;

    for (int i = 0; i < nums.size(); ++i)
      for (int j = 0; j < i; ++j)
        ans += count[nums[i] * nums[j]]++ * 8;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int tupleSameProduct(int[] nums) {
    int ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (int i = 0; i < nums.length; ++i)
      for (int j = 0; j < i; ++j) {
        final int prod = nums[i] * nums[j];
        ans += count.getOrDefault(prod, 0) * 8;
        count.merge(prod, 1, Integer::sum);
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def tupleSameProduct(self, nums: list[int]) -> int:
    # nums of ways to arrange (a, b) = 2
    # nums of ways to arrange (c, d) = 2
    # nums of ways to arrange (a, b), (c, d) = 2^3 = 8
    ans = 0
    count = collections.Counter()

    for i in range(len(nums)):
      for j in range(i):
        prod = nums[i] * nums[j]
        ans += count[prod] * 8
        count[prod] += 1

    return ans