JS, Python, Java, C++ | Fastest Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe trick to this problem is realizing that we can break it down into smaller pieces. A number can always be a leaf, so the number of **ways** it can form a branch should always start at **1**.\n\nIf the number can be made from multiple factor pairs, then **ways** is our starting value of **1** plus the sum of all the ways to make those factor pairs. \n\nFor each existing factor pair (**fA** & **fB**), the number of ways to make that that particular pair configuration is the product of the number of ways to make **fA** and **fB**.\n\nSo we can see that each number relies on first solving the same question for each of its factors. This means that we should start by sorting our numbers array (**A**). Then we can iterate through **A** and figure out each number in ascending order, so that we will have completed any factors for larger numbers before we need to use them.\n\nThis means storing the information, which we can do in a **map**, so that we can look up the results by value.\n\nIn order to be more efficient when we attempt to find each factor pair, we only need to iterate through **A** up to the **square root** of the number in question, so that we don\'t duplicate the same factor pairs going the opposite direction. That means we need to double every pair result where **fA** and **fB** are not the same.\n\nSince each number can be the head of a tree, our answer (**ans**) will be the sum of each number\'s result. We shouldn\'t forget to modulo at each round of summation.\n\n---\n\n#### ***Implementation:***\n\nJava and C++, having typed variables, should use **long** for **ways** and **ans**, but will need to cast **ans** back to **int** before returning. They will also need an extra **continue** conditional when checking for factors.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **96ms / 43.8MB** (beats 100% / 82%).\n```javascript\nvar numFactoredBinaryTrees = function(A) {\n    A.sort((a,b) => a - b)\n    let len = A.length, fmap = new Map(), ans = 0\n    for (let i = 0; i < len; i++) {\n        let num = A[i], ways = 1, lim = Math.sqrt(num)\n        for (let j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {\n            let fB = num / fA\n            if (fmap.has(fB))\n                ways = (ways + fmap.get(fA) * fmap.get(fB) * (fA === fB ? 1 : 2)) % 1000000007\n        }\n        fmap.set(num, ways), ans = (ans + ways) % 1000000007\n    }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **96ms / 14.4MB** (beats 99% / 74%).\n```python\nclass Solution:\n    def numFactoredBinaryTrees(self, A: List[int]) -> int:\n        A.sort()\n        fmap, ans = defaultdict(), 0\n        for num in A:\n            ways, lim = 1, sqrt(num)\n            for fA in A:\n                if fA > lim: break\n                fB = num / fA\n                if fB in fmap:\n                    ways += fmap[fA] * fmap[fB] * (1 if fA == fB else 2)\n            fmap[num], ans = ways, (ans + ways)\n        return ans % 1000000007\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **10ms / 38.7MB** (beats 99% / 91%).\n```java\nclass Solution {\n    public int numFactoredBinaryTrees(int[] A) {\n        Arrays.sort(A);\n        int len = A.length;\n        long ans = 0;\n        HashMap<Integer, Long> fmap = new HashMap<>();\n        for (int num : A) {\n            long ways = 1;\n            double lim = Math.sqrt(num);\n            for (int j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {\n                if (num % fA != 0) continue;\n                int fB = num / fA;\n                if (fmap.containsKey(fB))\n                    ways = (ways + fmap.get(fA) * fmap.get(fB) * (fA == fB ? 1 : 2)) % 1000000007;\n            }\n            fmap.put(num, ways);\n            ans = (ans + ways) % 1000000007;\n        }\n        return (int)ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **12ms / 9.1MB** (beats 100% / 81%).\n```c++\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& A) {\n        sort(A.begin(), A.end());\n        int len = A.size();\n        long ans = 0;\n        unordered_map<int, long> fmap;\n        for (int num : A) {\n            long ways = 1;\n            double lim = sqrt(num);\n            for (int j = 0, fA = A[0]; fA <= lim; fA = A[++j]) {\n                if (num % fA != 0) continue;\n                int fB = num / fA;\n                if (fmap.find(fB) != fmap.end())\n                    ways = (ways + fmap[fA] * fmap[fB] * (fA == fB ? 1 : 2)) % 1000000007;\n            }\n            fmap[num] = ways;\n            ans = (ans + ways) % 1000000007;\n        }\n        return (int)ans;\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']