Tuple with Same Product

Leetcode Problem:

• Tuple with Same Product

Summary

• Given an array 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 the array and a!= b!= c!= d.

Approach

• The approach used is to first filter out duplicate numbers from the input array
• Then, for each pair of numbers in the filtered array, calculate their product and store them in a vector
• Finally, count the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product.

Complexity

• O(n^2 log n) where n is the length of the input array

Explain

• The code first initializes a boolean array to keep track of duplicate numbers
• It then iterates over the input array and pushes each number into the boolean array if it's not already present
• This step is necessary to filter out duplicate numbers
• After that, the code sorts the filtered array and iterates over it to calculate the products of each pair of numbers
• The products are stored in a vector
• Finally, the code counts the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product
• The time complexity of this approach is O(n^2 log n) due to the sorting step.

Solution Code:

class Solution {
public:
    bool num[10001];
    int tupleSameProduct(vector& nums) {
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            if(num[nums[i]]){
                continue;
            }
            nums2.push_back(nums[i]);
            num[nums[i]] = true;
        }
        sort(nums2.begin(), nums2.end());
        vector nums3;
        for(int i = 0 ; i < nums2.size(); i++){
            for(int j = i+1 ; j < nums2.size(); j++){
                nums3.push_back(nums2[i] * nums2[j]);
            }
        }
        int ans = 0;
        sort(nums3.begin(), nums3.end());
        int cnt = 1;
        int cur = nums3[0];
        for(int i = 1 ; i < nums3.size();i++){
            cout << nums3[i] << endl;
            if(cur != nums3[i]){
                if(cnt >= 2){
                    ans += (cnt * (cnt - 1))/2 * 8;
                }
                cnt = 0;
            }
            cnt++;
            cur = nums3[i];
        }
        if(cnt >= 2){
            ans += (cnt * (cnt - 1))/2 * 8;
        }
        return ans;
    }
};