✅How to answer in interview✅ Intuition to Solution ✅ Beats 100%  ✅ Easier than other solutions
\n\n# YouTube Video Explanation:\nhttps://youtu.be/7l_j2ZrsUeM\n\n\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making com
![Screenshot 2023-10-26 095237.png](https://assets.leetcode.com/users/images/7343e9df-1ab1-40b4-a158-9b45567f48b4_1698294346.0528793.png)\n\n# YouTube Video Explanation:\n[https://youtu.be/7l_j2ZrsUeM](https://youtu.be/7l_j2ZrsUeM)\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 150 Subscribers*\n*Current Subscribers: 130*\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be solved by using dynamic programming. The idea is to iterate through the elements in the array, for each element, find all its potential factors, and then compute the number of binary trees that can be formed with the given element as the root. This can be done by considering the number of binary trees that can be formed with the factors as left and right subtrees.\n# Approach\n1. Sort the input array in ascending order.\n2. Initialize a variable `ans` to 0. This will store the total number of binary trees.\n3. Create a HashMap called `ways` to store the number of ways to form a binary tree for each element in the array. The key is the element itself, and the value is the number of ways.\n4. Iterate through the sorted array, for each element `x`:\n   a. Initialize `ways` to 1.\n   b. Calculate the maximum possible factor, `max`, which is the square root of `x`.\n   c. Iterate through the array starting from the smallest element (left factor).\n   d. For each left factor `left`, check if `x` is divisible by `left` (i.e., `x % left == 0`).\n   e. If `x` is divisible by `left`, calculate the right factor (`right`) as `x / left`.\n   f. Check if the `right` factor is present in the `ways` HashMap, and if so, update `ways` by adding the number of ways for `left` and `right`. Be careful to check if `left` and `right` are the same to avoid double-counting.\n   g. Update `ans` by adding `ways`.\n   h. Update the `ways` HashMap for the current element `x`.\n5. Return `ans % mod` to ensure the result is within the modulo range.\n\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(n * sqrt(max_value)), where `n` is the number of elements in the input array, and `max_value` is the maximum value in the array.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is O(n) to store the `ways` HashMap.\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n## Java\n```\nclass Solution {\n    int mod = (int)1e9+7;\n    public int numFactoredBinaryTrees(int[] arr) {\n        Arrays.sort(arr);\n        int ans =0;\n        HashMap<Integer, Long> map = new HashMap<>();\n\n        for(int x:arr)\n        {\n            long ways =1;\n            int max = (int)Math.sqrt(x);\n\n            for(int j = 0,left=arr[0];left<=max;left=arr[++j])\n            {\n                if(x%left!=0)   continue;\n                int right =x/left;\n                if(map.containsKey(right))\n                {\n                    ways = (ways+map.get(left)*map.get(right)*(left==right?1:2))%mod;\n                }\n            }\n            map.put(x,ways);\n            ans=(int)(ans+ways)%mod;\n        }\n        return ans;\n    }\n}\n```\n## C++\n```\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int mod = static_cast<int>(1e9 + 7);\n        std::sort(arr.begin(), arr.end());\n        int ans = 0;\n        std::unordered_map<int, long> map;\n\n        for (int x : arr) {\n            long ways = 1;\n            int max = static_cast<int>(std::sqrt(x));\n\n            for (int j = 0, left = arr[0]; left <= max; left = arr[++j]) {\n                if (x % left != 0) continue;\n                int right = x / left;\n                if (map.find(right) != map.end()) {\n                    ways = (ways + map[left] * map[right] * (left == right ? 1 : 2)) % mod;\n                }\n            }\n            map[x] = ways;\n            ans = (ans + static_cast<int>(ways)) % mod;\n        }\n        return ans;\n    }\n};\n```\n## Python\n```\nclass Solution(object):\n    def numFactoredBinaryTrees(self, arr):\n        mod = int(1e9 + 7)\n        arr.sort()\n        ans = 0\n        map = {}\n\n        for x in arr:\n            ways = 1\n            max_val = int(x ** 0.5)\n\n            j = 0\n            left = arr[0]\n            while left <= max_val:\n                if x % left != 0:\n                    j += 1\n                    left = arr[j]\n                    continue\n                right = x // left\n                if right in map:\n                    ways = (ways + map[left] * map[right] * (1 if left == right else 2)) % mod\n                j += 1\n                left = arr[j]\n            map[x] = ways\n            ans = (ans + ways) % mod\n\n        return ans\n        \n```\n## Javascript\n```\nvar numFactoredBinaryTrees = function(arr) {\n    const mod = 1e9 + 7;\n        arr.sort((a, b) => a - b);\n        let ans = 0;\n        const map = new Map();\n\n        for (const x of arr) {\n            let ways = 1;\n            const max = Math.sqrt(x);\n\n            for (let j = 0, left = arr[0]; left <= max; left = arr[++j]) {\n                if (x % left !== 0) continue;\n                const right = x / left;\n                if (map.has(right)) {\n                    ways = (ways + map.get(left) * map.get(right) * (left === right ? 1 : 2)) % mod;\n                }\n            }\n            map.set(x, ways);\n            ans = (ans + ways) % mod;\n        }\n        return ans;\n};\n```\n---\n![upvote1.jpeg](https://assets.leetcode.com/users/images/96d745ae-096b-4f04-b637-75ea06a3b1ba_1698294662.0177426.jpeg)\n
['Array', 'Hash Table', 'Dynamic Programming', 'Sorting', 'Python', 'C++', 'Java', 'JavaScript']