Tuple With Same Product - Leetcode Solution

Problem Statement:

Given an array nums of distinct integers, return all the tuples (a,b,c,d) such that:

1. 0 < a < b < c < d < nums.length
2. nums[a] * nums[b] = nums[c] * nums[d]
3. Return the answer in any order.

Example 1:

Input: nums = [2,3,4,6] Output: [[0,1,2,3],[0,2,1,3],[1,2,0,3]] Explanation: The tuples are:

• (nums[0], nums[1], nums[2], nums[3]) = (2, 3, 4, 6)
• (nums[0], nums[2], nums[1], nums[3]) = (2, 4, 3, 6)
• (nums[1], nums[2], nums[0], nums[3]) = (3, 4, 2, 6)

Example 2:

Input: nums = [1,2,4,5,10] Output: [[0,2,1,3],[0,3,1,4],[0,4,1,2],[1,3,2,4]] Explanation: The tuples are:

• (nums[0], nums[2], nums[1], nums[3]) = (1, 4, 2, 5)
• (nums[0], nums[3], nums[1], nums[4]) = (1, 5, 2, 10)
• (nums[0], nums[4], nums[1], nums[2]) = (1, 10, 2, 4)
• (nums[1], nums[3], nums[2], nums[4]) = (2, 5, 4, 10)

Solution Approach:

• Approach: Brute Force
• Create a list of tuples 4 digits long. Each digit in each tuple represents the index of an element in the input array, nums, (e.g. nums[tuple[0]]) that makes the following statement true: nums[tuple[0]] * nums[tuple[1]] == nums[tuple[2]] * nums[tuple[3]].
• Iterate over all combinations of 4 digits and add the tuple as a key to the dictionary with the product of the two pairs as an associated value.
• If the same product has already been seen, add the tuple and its corresponding product to the output list.

1