Simple DP solution in Java using hashmap and sorting, explained
Notes before approaching the problem -\n The key to this problem is not thinking of it as a tree problem at all. \n Just have to think of it as number of ways o
Notes before approaching the problem -\n* The key to this problem is not thinking of it as a tree problem at all. \n* Just have to think of it as number of ways of forming 3 numbers such that `number1 * number2 == number3 and number3 > number1 and number3 > number2`\n* The fact that you can use any number any number of times actually makes it easier than complex. You are saved from the hassle of deleting the number or marking it visited etc.\n\nImportant points while approaching the problem - \n* We need to give each element in the array a chance to be a root node and since its childrens\' multiplication is supposed to equal it, it is better if we sort the array and then move an `i` pointer ahead being the root and `j` pointer moving till `i`. ie) `i from 0 to array.length` and `j from 0 to i - 1`. \n* While moving with `i` pointer if we find a `j`  that divides `arr[i]`, then we might have a solution because - If `a * b == c`, where `a` is the `arr[j]` and `c` is the `arr[i]`, we have a solution because acco to the problem, `b` can be equal to `a` ie) can be repeated. If not, we can find a `b` eventually by setting a variable called `b= c / a` and see if it exists in the array and if it does, it is the other child of the a, b and c subtree/tree.\n* Use a hashmap to map elements to indexes while finding the `b` as said above\n* We can use a DP table to track this down where initially all elements of DP table are `1` because every element of the array without any children is a  tree in itself. If the last two points above help us find an `a, b, c` pair, update the `dp[c] = dp[a] * dp[b]` as it will cover all the cases like `c` being the root, `a` the right child and `b` left child and  `c` being the root, `a` the left child and `b` right child.\n* The final solution will be sum of values of the DP table. Take care of `long` in case of Java, CPP or C.\n\nJava code - \n\n```\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\n        int n = arr.length;\n        if(n == 1){\n            return 1;\n        }\n        Arrays.sort(arr);\n        \n        long[] dp = new long[n];\n        Arrays.fill(dp, 1);\n        \n        HashMap<Integer, Integer> map = new HashMap<>();\n        for(int i = 0; i < n; i++){\n            map.put(arr[i], i);\n        }\n        \n        long ans = 0;\n        int remaining = 0;\n        \n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < i; j++){\n                if(arr[i] % arr[j] == 0){\n                    remaining = arr[i] / arr[j];\n                    if(map.containsKey(remaining)){\n                        dp[i] += dp[j] * dp[map.get(remaining)];\n                    }\n                }\n            }\n        }\n        \n        for(long v : dp){\n            ans += v;\n        }\n        return (int) (ans % 1_000_000_007);\n    }\n}\n```
['Dynamic Programming', 'Sorting', 'Java']