Tuple with Same Product

Intuitionwhy equal-product pairs already contain the whole counting problem

Start with one unordered pair of distinct values, such as {a, b}. Its product identifies the pair. Because all values in nums are distinct and positive, two different pairs with the same product cannot share an element: if a * b = a * c, then b = c. Therefore, every pair in one product group is automatically disjoint from every other pair in that group.

Suppose a product occurs for f unordered pairs. Choose any two of those pairs, giving f * (f - 1) / 2 choices. Each chosen pair can be ordered in two ways, and the two pair positions can be swapped, so each choice creates 2 * 2 * 2 = 8 tuples. The contribution is therefore f * (f - 1) / 2 * 8 = 4f(f - 1). Hashing lets you collect those frequencies without comparing every pair against every other pair.

Approachbuild product frequencies, then count pair combinations

1. 1Enumerate every unordered pair of indices i and j with i < j, because using both orders would count the same value pair twice before tuple ordering is even considered.
2. 2Compute nums[i] * nums[j] and increment its frequency in a hash map, because pairs with the same product are exactly the pairs that can form a valid tuple.
3. 3After all pairs are grouped, visit each frequency f and choose two different pairs from that group in f * (f - 1) / 2 ways; choosing the same pair twice would reuse its elements.
4. 4Multiply each pair choice by 8, because the two values inside each pair can be ordered independently and the two pairs can occupy either side of the equality.
5. 5Accumulate 4 * f * (f - 1) directly, which is the same calculation after cancelling the factor of 2 in the combination count.
6. 6Return the accumulated answer after every product group has contributed; no individual tuple needs to be stored, so the counting stays compact.

Complexityn is the number of values in nums

Annotated solutionC++ · two-pass hashing · count frequencies before converting them to tuples

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> freq;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ++freq[nums[i] * nums[j]];
            }
        }

        int answer = 0;
        for (const auto& entry : freq) {
            int f = entry.second;
            answer += 4 * f * (f - 1);
        }

        return answer;
    }
};

The one-pass alternativethe same work with the combination count applied as pairs arrive

You can avoid the second scan by processing each unordered pair as soon as it is generated. If the current product has already appeared f times, the new pair forms f new selections with earlier pairs, and each selection contributes 8 tuples. Add 8 * f, then increment the frequency. This is merely a different arrangement, not an optimisation: it keeps the same O(n^2) time and O(n^2) worst-case extra space.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> freq;
        int answer = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int product = nums[i] * nums[j];
                int previous = freq[product];
                answer += 8 * previous;
                ++freq[product];
            }
        }

        return answer;
    }
};

Common mistakesthe two counting errors that change the answer