Skip to main content

Hashing

Tuple with Same Product Solution In C++/Java/Python/Javascript

Problem Description

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

Problem Explanation

what is tuple?
A group of immutable elements is called tuple. This term is specifically used in python. In fact, there is data structure with same name in python.
for eg: (1, 2, 3, 4), (8, 11, 34, 5), … so on are tuple of size 4

So, We are given an array nums of distinct positive integers. We need to find the number of tuples (a, b, c, d) such that: a * b = c * d
All elements in the tuple are distinct: a != b != c != d. Here, a, b, c, and d are elements of nums.

Example

Input: nums = [1, 3, 9, 27]
Output: 8
Explanation:
Generate all possible tuples of size 4 whose product i.e (axb) = (cxd):
Valid tuples are: (1, 27, 3, 9), (1, 27, 9, 3), (27, 1, 3, 9), (27, 1, 9, 3), (3, 9, 1, 27), (9, 3, 1, 27), (3, 9, 27, 1), (9, 3, 27, 1)
Final Output: 8

Input: nums = [1, 2, 3, 6]
Output: 1
Explanation:
Generate all possible pairs of numbers and their products:
1 × 2 = 2, 1 × 3 = 3, 1 × 6 = 6, 2 × 3 = 6, 2 × 6 = 12, 3 × 6 = 18
Pairs and their products: {2: [(1, 2)], 3: [(1, 3)], 6: [(1, 6), (2, 3)], 12: [(2, 6)], 18: [(3, 6)]}
Check for products that appear more than once: Product 6 appears twice: Pairs are (1, 6) and (2, 3). Form valid tuples: From pairs (1, 6) and (2, 3), a valid tuple is (1, 6, 2, 3).
Count the valid tuples: There is 1 valid tuple: (1, 6, 2, 3).

Constraints

1 <= nums.length <= 103
1 <= nums[i] <= 104
All elements in nums are distinct.

💡
Try it Yourself First
While this problem might seem complex at first glance, there are systematic strategies to tackle it. You can approach it using Recursion to fina all possible tuples such that (a * b == c * d)  or you calculate their products, using a hashmap to efficiently track occurrences of each product, and then identifying overlapping pairs to form valid tuples. This method balances clarity of implementation with computational efficiency, offering an intuitive way to solve the problem step by step.

Brute Force Approach

Intuition

The problem requires finding tuples (a,b,c,d)(a, b, c, d)(a,b,c,d) in the input array such that the product of two numbers equals the product of another two numbers (a×b=c×d).
To solve this, we need to consider all possible groups of four numbers from the array and check if their product conditions are satisfied. One way to do this is by generating all permutations of four numbers and verifying the product condition for each permutation.

Approach

Understanding Tuples and Permutations:
The goal is to generate all possible permutations and verify whether the product of the first two numbers equals the product of the last two numbers.

Recursive Permutation Function:
To solve the problem of generating all possible permutations of an input array with a specific condition of including only permutations of size 4, we rely on recursion and the concept of swapping elements. The approach involves a helper function, named permutation, which handles the recursive process of creating every possible arrangement of the array elements.

The recursive function works by swapping elements in the array to rearrange their order systematically. At each step, we fix one element at a specific position and recursively generate permutations for the remaining elements. This ensures that every possible combination is explored. For example, if the input array has elements [a, b, c, d], the function will first fix a at the start and generate permutations of [b, c, d]. Then, it will fix b at the start, swapping it with a, and generate permutations for the rest, and so on.

A base case is necessary to stop the recursion. In this case, when the size of the current permutation reaches 4, it is added to the result. This ensures that only tuples of the desired size are included. The recursive swapping continues until all elements are considered, and all unique permutations are created.

Backtracking:
To generate all permutations, swap elements at different positions in the array. After processing one permutation, undo the swaps (backtracking) to reset the array for the next permutation.

This is how sudo code will look like:
Note: Consider fun function is calculating all possible permutations of array of size 4. [arr ⇒ Given array, ds ⇒ 2d matrix storing all possible array we can form by permutation of given array, idx ⇒ starting index i.e 0 ]
Pseudo Code:

fun(idx, ds, arr){
 // Base Case
 for( i = 0 to n - 1)
  swap(arr[idx], arr[i]);
 fun(idx + 1, ds, arr);
 // Backtrack approach to revert back the same array we had swapped initially
 swap(arr[idx], arr[i]);
}

Validation of Tuples:
For each generated tuple, check whether a×b=c×d. If the condition holds, increment the count of valid tuples.

Return the Result: Finally, return the count of valid tuples.

Example
Input: nums = [2, 3, 4, 6]
Step-by-Step Process:
Generate all permutations of the array: Possible permutations include [2,3,4,6][2, 3, 4, 6][2,3,4,6], [2,3,6,4][2, 3, 6, 4][2,3,6,4], [2,4,3,6][2, 4, 3, 6][2,4,3,6], and many more.
Check the product condition for each tuple: For the tuple [2,3,4,6][2, 3, 4, 6][2,3,4,6]: 2×3=6, 4×6=24 (Condition not satisfied).
For the tuple [2,6,3,4][2, 6, 3, 4][2,6,3,4]: 2×6=12, 3×4=12 (Condition satisfied).
Count valid tuples: Only one tuple satisfies the condition, so the count is 1.
Output: 1

Dry Run

Let’s take a unique example:
Input: nums = [2, 4, 6, 12]

Step 1: Calculate all pair products
We calculate all pairs and their products, storing them in a hashmap:
First, we take the pair formed by the elements at indices (0, 1), which correspond to the values (2, 4) in the array. Multiplying these values gives us a product of 2 × 4 = 8. Next, we move to the pair (0, 2), which corresponds to the values (2, 6). Their product is 2 × 6 = 12. Similarly, for the pair (0, 3), representing the values (2, 12), the product is 2 × 12 = 24.

Continuing the process, we calculate the product for the pair (1, 2), representing the values (4, 6). Here, the product is 4 × 6 = 24. For the pair (1, 3), corresponding to the values (4, 12), the product is 4 × 12 = 48. Lastly, the pair (2, 3), with the values (6, 12), gives a product of 6 × 12 = 72.
Key-Value pairs of products: { 8: [(0, 1)], 12: [(0, 2)], 24: [(0, 3), (1, 2)], 48: [(1, 3)], 72: [(2, 3)] }

Step 2: Count the tuples
For each product in the hashmap: If there is more than one pair for the product, count the number of valid tuples.
Starting with the product 8, it is derived from a single pair [(0, 1)]. Since there’s only one pair, no tuples can be formed, and the number of tuples is 0. Similarly, for the product 12, which comes from the pair [(0, 2)], there’s only one pair, so no tuples are formed here either, resulting in 0 tuples. The product 24, however, comes from two distinct pairs: [(0, 3), (1, 2)]. These two pairs allow us to form tuples by permuting them. Specifically, there are 4 permutations possible, as each of the two pairs contributes to the total. Thus, the number of tuples for this product is calculated as 4 × 1 = 4.
For the product 48, derived from the pair [(1, 3)], only one pair exists, and similar to the earlier cases with single pairs, no tuples can be formed, resulting in 0 tuples. Finally, the product 72 comes from the pair [(2, 3)], which also has just one pair, leaving no possibility for tuple formation, resulting in 0 tuples.
Total Count: 4

Step 3: Output
The total number of valid tuples is 4

Code for All Languages
C++ 
class Solution {
private: 
    // Tuple with Same Product solution in C++
    void permutation(vector<vector<int>> &per, vector<int> &nums, int idx) {
        // Base case: to form tuples of 4 elements only
        if(idx == 4) {
            // once tuple forms push it main container having all such tuples
            per.push_back(nums);

            return;
        }
        for(int i = idx; i < nums.size(); ++i) {
            // swap the elements to make all possible permutations possible
            swap(nums[i], nums[idx]);

            // move to the nex index element and start finding their permutation
            permutation(per, nums, idx + 1);

            // backtrack to undo those swapped elements performed before
            swap(nums[i], nums[idx]);
        }
    }
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
        // TC = n^n
        vector<vector<int>> per;

        // call the permutation function to generate all possible tuples
        permutation(per, nums, 0);

        // store the count of all such tuples here
        int count = 0;

        // Iterate over all possible tuples
        for(auto &v : per) {

            // check if a * b == c * d and keep counting
            if(v[0] * v[1] == v[2] * v[3]) ++count;
        }
        // print the result
        return count;
    }
};

Java 
class Solution {
    // Tuple with Same Product solution in Java
    private void permutation(List<List<Integer>> per, List<Integer> nums, int idx) {
        // Base case: to form tuples of 4 elements only
        if (idx == 4) {
            // Once tuple forms, push it to the main container having all such tuples
            per.add(new ArrayList<>(nums));
            return;
        }
        for (int i = idx; i < nums.size(); ++i) {
            // Swap the elements to make all possible permutations
            Collections.swap(nums, i, idx);

            // Move to the next index element and start finding their permutation
            permutation(per, nums, idx + 1);

            // Backtrack to undo those swapped elements performed before
            Collections.swap(nums, i, idx);
        }
    }

    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        // TC = n^n
        List<List<Integer>> per = new ArrayList<>();
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) numsList.add(num);

        // Call the permutation function to generate all possible tuples
        permutation(per, numsList, 0);

        // Store the count of all such tuples here
        int count = 0;

        // Iterate over all possible tuples
        for (List<Integer> v : per) {
            // Check if a * b == c * d and keep counting
            if (v.get(0) * v.get(1) == v.get(2) * v.get(3)) ++count;
        }
        // Return the result
        return count;
    }
}

Python 
class Solution:
    # Tuple with Same Product Solution in Python
    def permutation(self, per, nums, idx):
        # Base case: to form tuples of 4 elements only
        if idx == 4:
            # Once tuple forms, push it to the main container having all such tuples
            per.append(nums[:])
            return
        
        for i in range(idx, len(nums)):
            # Swap the elements to make all possible permutations
            nums[i], nums[idx] = nums[idx], nums[i]

            # Move to the next index element and start finding their permutation
            self.permutation(per, nums, idx + 1)

            # Backtrack to undo those swapped elements performed before
            nums[i], nums[idx] = nums[idx], nums[i]

    def tupleSameProduct(self, nums):
        n = len(nums)
        # TC = n^n
        per = []

        # Call the permutation function to generate all possible tuples
        self.permutation(per, nums, 0)

        # Store the count of all such tuples here
        count = 0

        # Iterate over all possible tuples
        for v in per:
            # Check if a * b == c * d and keep counting
            if v[0] * v[1] == v[2] * v[3]:
                count += 1
        
        # Return the result
        return count

Javascript 
class Solution {
    // Tuple with Same Product Solution in JavaScript
    permutation(per, nums, idx) {
        // Base case: to form tuples of 4 elements only
        if (idx === 4) {
            // Once tuple forms, push it to the main container having all such tuples
            per.push([...nums]);
            return;
        }
        for (let i = idx; i < nums.length; ++i) {
            // Swap the elements to make all possible permutations
            [nums[i], nums[idx]] = [nums[idx], nums[i]];

            // Move to the next index element and start finding their permutation
            this.permutation(per, nums, idx + 1);

            // Backtrack to undo those swapped elements performed before
            [nums[i], nums[idx]] = [nums[idx], nums[i]];
        }
    }

    tupleSameProduct(nums) {
        const n = nums.length;
        // TC = n^n
        const per = [];

        // Call the permutation function to generate all possible tuples
        this.permutation(per, nums, 0);

        // Store the count of all such tuples here
        let count = 0;

        // Iterate over all possible tuples
        for (const v of per) {
            // Check if a * b == c * d and keep counting
            if (v[0] * v[1] === v[2] * v[3]) count++;
        }
        // Return the result
        return count;
    }
}

Time Complexity: O(n!)

To generate all permutations of size 4, the function considers P(n, 4) , which represents the numbers of ways to arrange 4 elements from a set of n elements. Mathematically, this is calculated as: P(n, 4) = n! / (n - 4)!

Here, n! represents factorial of n, and (n - 4)! refers to permutations which doesn’t contribute to arrangements of size 4.

Each permutation is generated through recursive swapping of elements. Since swapping and processing each permutation take constant time, the overall time complexity is proportional to the number of permutations. Thus, the time complexity for generating permutations is: O(P(n, 4)) = O(n! / (n - 4)!)

Space Complexity: O(n!)

The space complexity is influenced by two factors: storing the permutations and the auxiliary space used by the recursion stack.

For Storing Permutations all P(n,4) permutations are stored in a list. Each permutation is an array of size 4. Therefore, the space required for storage is: O(P(n, 4)) = O(n! / (n - 4)!)

For recursion stack space is used also called Auxiliary Space, since the recursive function processes n elements, the depth of the recursion stack is proportional to n. Hence, the space required for recursion is: O(n!)

The brute force approach will work correctly and also will be able to pass some test cases. However for larger test cases where number of iterations going beyond 1e8 (1 sec, no. of iterations possible ~ 1e8) will give TLE (time limit exceeded). Therefore, we need to think of better approach which work for all test cases and don’t throw TLE. And that can happen only if we solve the problem using minimum number of for loop in nesting.

Optimal Approach

Intuition

The problem asks us to find tuples (a, b, c, d) from the given array nums such that a×b=c×d, where a,b,c,d are distinct elements.

Key Observation:
If two pairs of numbers (a,b) and (c,d) produce the same product P=a×b=c×d, then we can count all such pairs. Each unique product value P represents a group of pairs that can form tuples satisfying the condition.

Combination and Permutation:
Suppose for a product P, there are k pairs (a,b). We can choose 2 out of these k pairs in C(k,2)= = (k×(k−1))/2​ ways.
kC2 = K! / (2!) x (K - 2)! = (K x (K - 1) x (K-2)!) / ((2!) x (K-2)!) = (K x (K - 2))/2 [So, here (K-2)! gets cancels out from top and bottom.

Above value kC2 is a Combination concepts (to learn more you can find out here)
Once we have two pairs, the number of ways to arrange 4 elements (a,b,c,d)(a, b, c, d)(a,b,c,d) is 8 because each pair can swap places.

Approach:
Calculate all possible products of pairs from the array using two nested loops. Store the frequency of each product in a hash map. For each product with frequency F > 1, compute the number of tuples using combinations and permutations. Return the total count of such tuples.

Approach

Step 1: Initialization

  • n = nums.size() gets the size of the input array.
  • Create a map mp to store the frequency of each product.
  • Create a variable ans = 0 to store the final count of tuples.

Step 2: Compute Pairwise Products (Outer and Inner Loops)
Use two nested loops to iterate over all pairs of elements in the array:

  • Outer loop runs from i = 0 to n - 1.
  • Inner loop runs from j = i + 1 to n - 1.
  • Calculate the product of nums[i] and nums[j] and store it in a variable product.
  • Update the frequency of product in the map mp[product]++.

Step 3: Traverse the Map to Count Tuples Iterate through the map mp to process all unique products. 

  • For each product, check its frequency productCount = pr.second. 
  • If productCount > 1, calculate the number of ways to choose two pairs: 
    Use the combination formula C(productCount , 2) = productCount x (productCount - 1) / 2 .
  • Multiply this result by 8 (to account for permutations) and add it to ans.

Step 4: Return the Final Result
Multiply the total combinations by 8 and return the result stored in ans.

Dry Run

Let’s dry-run the code with an example:
Input: nums = [2, 3, 4, 6]

Step 1: Compute all pairwise products and their frequencies
Loop through all pairs in nums: 2×3=6 → product 6, count = 1, 2×4=8 → product 8, count = 1, 2×6=12 → product 12, count = 1, 3×4=12 → product 12, count = 2, 3×6=18 → product 18, count = 1, similarly, 4×6=24 → product 24, count = 1
Map after Step 1: { 6 : 1, 8 : 1, 12 : 2, 18 : 1, 24 : 1 }

Step 2: Count tuples for each product
For each product, if its frequency f>1: Compute C(f,2) : for 12, f = 2 → C(2,2) = 1. Then multiply by 8 (permutations for the tuple).
Why to multiply by 8?
Reason: Because for every valid tuple (of size = 4) there are 8 possible valid permutations of such elements which satisfies a x b = c x d

For eg: Tuples for product 12: Possible pairs: (2,6) , (3,4), Tuples: (2,6,3,4), (2,6,4,3), (6,2,3,4), (6,2,4,3) and vice versa for (3,4). So, Total = 1 x 8 = 8.

Final Answer: 8.
If you still feel confused of why we multiplied with 8.
Lets take another example: tuple = (2, 3, 6, 1)

  • Consider we have 4 numbers and we have to fill those 4 boxes to make up a tuple.
  • To fill first box we have 4 choices. We can pick of 4.
  • Now, to fill second box we have only 1 choices. How you ask? Because lets say in first box you picked 2 then in next box you are bound to pick 3 in order to make there product equal to 6 so that other two elements product can become equal.
  • Similarly to we have 2 choices to fill third box. Because after fill first two boxes we are left with only two elements.
  • Finally we have 1 choice  to fill the last or fourth box.

Now using rule of multiplication to find all possible permutations:
we get, 4 x 1 x 2 x 1 = 8 
And thats how my friend we have 8 permutations for each unique tuple.

Code for All Languages
C++ 
class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        // size of nums array
        int n = nums.size();

        // to store the frequency of every unique occurence of elements
        map<int, int> mp;

        // Applying nested loops to get all possible two elements at a time
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j) {
                // we will get two different elements of nums at a time
                int product = nums[i] * nums[j];

                // keep counting all different products
                mp[product]++;
            }
        }
        // stores our answer count
        int ans = 0;
        for(auto &pr : mp){
            int productCount = pr.second;

            // Based on Combination concepts: total ways of choosing two out of productCount (or n) is nC2 = (n * (n - 1))/2
            ans += (productCount * (productCount - 1))/2;
        }
        // total ways of getting all possible permutation for given tuple of 4 will be 8 such that criteria of (a x b) = (c x d) satisfies.
        return ans * 8;
    }
};

Java 
import java.util.*;

class Solution {
    public int tupleSameProduct(int[] nums) {
        // size of nums array
        int n = nums.length;

        // to store the frequency of every unique occurrence of elements
        Map<Integer, Integer> mp = new HashMap<>();

        // Applying nested loops to get all possible two elements at a time
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // we will get two different elements of nums at a time
                int product = nums[i] * nums[j];

                // keep counting all different products
                mp.put(product, mp.getOrDefault(product, 0) + 1);
            }
        }

        // stores our answer count
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int productCount = entry.getValue();

            // Based on Combination concepts: total ways of choosing two out of productCount (or n) is nC2 = (n * (n - 1)) / 2
            ans += (productCount * (productCount - 1)) / 2;
        }

        // total ways of getting all possible permutation for given tuple of 4 will be 8 such that criteria of (a x b) = (c x d) satisfies.
        return ans * 8;
    }
}

Python 
from collections import defaultdict

class Solution:
    def tupleSameProduct(self, nums):
        # size of nums array
        n = len(nums)

        # to store the frequency of every unique occurrence of elements
        mp = defaultdict(int)

        # Applying nested loops to get all possible two elements at a time
        for i in range(n):
            for j in range(i + 1, n):
                # we will get two different elements of nums at a time
                product = nums[i] * nums[j]

                # keep counting all different products
                mp[product] += 1

        # stores our answer count
        ans = 0
        for productCount in mp.values():
            # Based on Combination concepts: total ways of choosing two out of productCount (or n) is nC2 = (n * (n - 1)) // 2
            ans += (productCount * (productCount - 1)) // 2

        # total ways of getting all possible permutation for given tuple of 4 will be 8 such that criteria of (a x b) = (c x d) satisfies.
        return ans * 8

Javascript 
class Solution {
    tupleSameProduct(nums) {
        // size of nums array
        const n = nums.length;

        // to store the frequency of every unique occurrence of elements
        const mp = new Map();

        // Applying nested loops to get all possible two elements at a time
        for (let i = 0; i < n; ++i) {
            for (let j = i + 1; j < n; ++j) {
                // we will get two different elements of nums at a time
                const product = nums[i] * nums[j];

                // keep counting all different products
                mp.set(product, (mp.get(product) || 0) + 1);
            }
        }

        // stores our answer count
        let ans = 0;
        for (const productCount of mp.values()) {

            // Based on Combination concepts: total ways of choosing two out of productCount (or n) is nC2 = (n * (n - 1)) / 2
            ans += (productCount * (productCount - 1)) / 2;
        }

        // total ways of getting all possible permutation for given tuple of 4 will be 8 such that criteria of (a x b) = (c x d) satisfies.
        return ans * 8;
    }
}

Time Complexity: O(n2) x O(logn)

  • Nested loop (two loops: one loop inside another loop) will loop for NxN times i.e N2 times. 
  • Also the map we use to store the frequency will take O(1) in unordered_map in c++ or more precisely O(logn) [in case of map in c++ similarly for other data structure in different languages].
  • Next we have another for loop which runs O(N) times

Overall we add up all those, then final Time complexity = O(N2)xO(logN) + O(N) = O(N2)xO(logN)
However, if we use unodered_map in our code then our time complexity will be O(N2) xO(1) = O(N2) only
(why O(logN) multiplied ? because we are incrementing count of each product inside the nested for loop)

Space Complexity: O(n2)

The most significant additional memory usage comes from the map (or dictionary, hash map, etc., depending on the programming language).
The maximum number of unique keys in the map depends on the total number of pairs (i, j) that can be formed. 
In the worst case:
1) There are nC2 = n * (n - 1) / 2 pairs
2) If every pair produces a unique product (which happens if all elements are distinct and their pairwise products are distinct), there will be nC2 unique entries in the map.
So, it will effectively take O(N2) space. Beside this all other variables will take O(1) space.
In total Space Complexity = O(N2)

Learning Tip

Since, we have fully understood and solved the above problem. Let's try out this interesting problem utilizes same idea we discussed.

Equal Row and Column Pairs

Given an n x n matrix grid, return the number of pairs (r, c) where row r and column c are equal. A row and column are considered equal if all elements in the row are the same as the corresponding elements in the column.

4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4, all of length n, return the number of tuples (i, j, k, l) such that:
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.