Krammer's blog

https://leetcode.com/problems/tuple-with-same-product/ from Google

Thinking process:

The constraint tells us that we can use O(N^2) solution. So we iterate through all possible pair of number, which is O(N^2). Count how many of them have the same product. Finally, we use N choose 2 formula to compute the number of tuples as we can pick any two of them to make the tuple. Don’t forget to time the result by 4 as they can swap the order.

Here is the code.

 1class Solution {
 2public:
 3    int tupleSameProduct(vector<int>& nums) {
 4        int N = nums.size();
 5        int ans = 0;
 6        unordered_map<int, int> cnt;
 7        for (int i=0; i<N; i++) {
 8            for (int j=i+1; j<N; j++) {
 9                if (i == j) continue;
10                cnt[nums[i]*nums[j]]++;
11            }
12        }
13        for (auto [k, v] : cnt) {
14            ans += (v)*(v-1)*4;
15        }
16        return ans;
17    }
18};

Editorial: LeetCode 1726 Tuple With Same Product