Question: Given an array of integers and an integer *x*, I need to find the number of unordered triples in the array whose product is *x*. I have a brute-force O(*n*3) solution:

```
int solve(int a[], int n, int x) {
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            for (int k = j+1; k < n; ++k)
                if(a[i]*a[j]*a[k] == x)
                    ans++;
    return ans;
}

```

Is there a faster way to do this, say in O(*n* log *n*) time?

Answer: 
You could 

1. put all elements in a into a hashtable -- O(n)
2. Factorize x -- O(sqrt(x))
3. Build all possible triplets of divisors of x -- O(3^log(x))
4. Search for these triplets in your Hashtable -- O(1)
5. If a triplet exists, increase your counter -- O(1)

The runtime will now be dependent on the number of prime factors pf(x) of x, specifically O(3^pf(x)). Since the number of prime factors of x can be bounded by log(x) this yields **O(3^log(x))** which could actually simplify further dependent on the exact base.
Code is in java but as you know, the idea remains the same. 

Time complexity is `O(n^1.5)`. I checked this with 10^5 elements and it works ok. 
The idea is-

* Put all elements of the list with their count in a map.
* Now, if `a[i]*a[j]*a[k] == x` to be `true`, all these 3 have to be factors of `x`. Hence, if `x%a[i] == 0`, I hunt for checking all factors(pairs) that multiply to `x/a[i]` in `sqrt(x/a[i])` time.
* Since, we do it for every element in the list, complexity goes like this- 

	+ O(n) for adding elements to map.
	+ O(n \* n^0.5) for checking triplets.

So, total complexity = O(n) + O(n \* n^0.5) = O(n^1.5) asymptotically.

**ASSUMPTION** - I am considering tuples as triplets having different indices in the array.

**UPDATE** - Current code considers different permutations of the same indices `i,j,k` as different tuples. You can fix it by having an additional map storing triplet indices as a string by joining them `|` (pipe) separated. 

```
import java.util.*;
import java.io.*;
class Solution{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split("\\s");
        int[] a = new int[n];
        for(int i=0;i<n;++i){
            a[i] = Integer.parseInt(s[i]);
        }
        int x = Integer.parseInt(br.readLine());
        System.out.println(solve(a,n,x));
    }

    private static long solve(int a[], int n, int x) {
        long tuples = 0;
        Map<Integer,Integer> elements = new HashMap<>();

        for(int i=0;i<a.length;++i){
            elements.put(a[i],elements.getOrDefault(a[i],0) + 1);
        }

        for(int i=0;i<a.length;++i){
            if(x%a[i] == 0){
                tuples += factorPairs(x/a[i],elements,a[i]);
            }
        }

        return tuples;
    }

    private static long factorPairs(int x,Map<Integer,Integer> elements,int factor1){
        long pairs = 0;
        for(int i=1;i*i<=x;++i){
            int second = i;
            int third = x/i;
            if(second*third == x && elements.containsKey(second) && elements.containsKey(third)){
                long second_cnt = elements.get(second) - (second == factor1 ? 1 : 0);
                long third_cnt = elements.get(third) - (third == factor1 ? 1 : 0);
                pairs += second_cnt * third_cnt;
            }
        }

        return pairs;   
    }
}

```