Skip to content

← leetcode

Tuple with Same Product

· Medium

LeetCode problem 1726

I like to hash out a plan to map out my solution for upcoming leetcode questions. Yes, it is a hash-map problem.

Problem itself is quite straightforward once you see the vision:

  • we can iterate through all possible pairs to find all the possible products and store the frequency of each one in a hash-map
  • then, we can iterate through all the [key, value] pairs of the unordered_map. If we let the frequency of a product be denoted by n, then the number of valid tuples that can be formed is just (n)*(n-1)*4.
    • this can be easily derived after realising that there are n choices for the pair [a, b], meaning there will remain n-1 choices for the pair [c, d]. Then, since we can rearrange the order of [a, b] and [c, d] (e.g. a * b is the same as b * a), we get n * (n-1) * 2 * 2 = n * (n-1) * 4 as expected.

code

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> mp;
        int ans = 0;

        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i+1; j < nums.size(); ++j) {
                ++mp[nums[i] * nums[j]];
            }
        }

        for (auto &multiple : mp) {
            ans += (multiple.second * (multiple.second-1)) * 4;
        }

        return ans;
    }
};

complexity

  • Time: O(n^2)
  • Space: O(n^2)