Subtask 1

For this subtask, we can brute force all ~4~-tuples. Make sure that all indices used are distinct for each tuple.

Time Complexity: ~\mathcal O(N^4)~

Subtask 2

For this subtask, we can brute force the first three elements ~(i, j, k)~ of the tuple. We can compute ~d = \frac{a_i \times a_j}{a_k}~, and find out how many times ~d~ shows up in the array. We need to subtract ~1~ for each of ~a_i = d~ or ~a_j = d~ or ~a_k = d~.

Time Complexity: ~\mathcal O(N^3)~

Subtask 3

For this subtask, we can loop through the first two elements ~(i, j)~ of the tuple. We can store how many times the product ~p = a_i \times a_j~ appears.

Then, we can loop through the first two elements ~(i, j)~ again. We can add to the total the number of times ~a_i \times a_j~ shows up across all other pairs.

Unfortunately, we might over-count any pairs ~(i, k)~ or ~(j, k)~, so we can use a frequency array to exclude those.

Also, we have removed the pair ~(i, j)~ too many times, so we should add ~2~ back to our total.

Finally, we also have to add back pairs if ~a_i = a_j~, since then the pairs ~(i, j)~ and ~(j, i)~ are excluded too many times.

Time Complexity: ~\mathcal O(N^2)~

Note: Although the complexity of this problem is ~\mathcal O(N^2)~, most solutions use a map and perform very poorly. A harder version of this problem exists to challenge those who are interested. Hint: don't use a map.