🔥Efficient Method🔥| Explained Intuition & Approach | Java | C++ | Python | JavaScript | C# | PHP
Intuition \uD83D\uDE80\n Describe your first thoughts on how to solve this problem. \nThe key idea here is to use dynamic programming to count the number of val
# Intuition \uD83D\uDE80\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key idea here is to use dynamic programming to count the number of valid binary trees efficiently. The intuition is as follows:\n\n1. Sort the input array: Start by sorting the array in ascending order because you need to consider factors from small to large values for dynamic programming.\n\n2. Initialize a dynamic programming map: Create a map to store the number of binary trees that can be formed with each element as the root node. Initialize the values in the map with 1 because each element can be a valid tree on its own.\n\n3. Dynamic Programming: Iterate through the sorted array, and for each element, iterate through all previous elements as potential factors. If a factor exists, update the number of binary trees ending with the current element by considering the factor\'s contribution. The dynamic programming formula used in this code is based on the principle that if you have two factors (j and i/j), you can form `dp[j] * dp[i/j]` new binary trees that end with the current element.\n\n4. Calculate the final result: Sum up all the values in the dynamic programming map to get the total number of valid binary trees.\n\n\n# Approach \uD83D\uDE80\n<!-- Describe your approach to solving the problem. -->\n1. Sort the array in ascending order to consider factors from small to large values.\n\n2. Create a set to store unique numbers in the array. This set helps in faster containment checks.\n\n3. Initialize a dynamic programming map (`dp`) where the keys are array elements, and the values are the number of binary trees ending with that element. Initialize all values to 1, indicating that each element can form a single tree by itself.\n\n4. Iterate through the array elements:\n   - For each element `i`, iterate through the elements that precede it (`j`).\n   - If `j` is larger than the square root of `i`, break the loop because further `j` values won\'t be factors.\n   - Check if `j` is a factor of `i` and if `i/j` is in the set of unique numbers.\n   - Update the number of binary trees ending with `i` based on the factors `j` and `i/j` using the dynamic programming formula. This accounts for the new trees that can be formed using the factors.\n\n5. Calculate the final result by summing up all the values in the dynamic programming map and return the result modulo 1000000007 (as specified in the problem).\n\nThe below code is an efficient implementation of this approach, using dynamic programming to count the valid binary trees while considering all possible factors and combinations.\n\n\n# Complexity \uD83D\uDE81\n## \uD83C\uDFF9Time complexity: $$O(n * sqrt(max(arr)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. **Sorting:** The initial step involves sorting the input array. The time complexity for this is $$O(n * log(n))$$, where \'n\' is the number of elements in the array.\n\n2. **Dynamic Programming:** The main loop involves nested loops, where you iterate through all elements of the input array. In the worst case, for each element \'i\', you iterate through all previous elements \'j\' up to the square root of \'i\'. So, the time complexity of this part is $$O(n * sqrt(max(arr)))$$ where \'n\' is the number of elements in the array, and \'max(arr)\' is the maximum element in the array.\n\n3. **Final Summation:** After completing the dynamic programming, you iterate through all values in the `dp` map to calculate the final result. This requires iterating through \'n\' elements in the map. This step contributes $$O(n)$$ to the time complexity.\n\nCombining these steps, the overall time complexity is $$O(n * log(n)) + O(n * sqrt(max(arr))) + O(n)$$, which can be simplified to $$O(n * sqrt(max(arr))).$$\n\n\n## \uD83C\uDFF9Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n1. **Sorting:** Sorting the input array in-place doesn\'t require any additional space, so this step has a space complexity of $$O(1).$$\n\n2. **Set for Unique Numbers:** You create a set `uniqueNumbers` to store unique elements from the input array. In the worst case, if all elements are unique, this set would have \'n\' elements. Therefore, the space complexity of this set is $$O(n).$$\n\n3. **Dynamic Programming Map:** You create a map `dp` to store values for each element in the input array. In the worst case, there can be \'n\' key-value pairs in the map. So, the space complexity for the map is $$O(n).$$\n4. \nCombining these factors, the overall space complexity of the code is $$O(n)$$ due to the sets and maps created.\n\n# Code \u2712\uFE0F\n``` Java []\npublic class Solution {\n    private static final int MOD = 1000000007;\n\n    public int numFactoredBinaryTrees(int[] arr) {\n        // Step 1: Sort the input array in ascending order.\n        Arrays.sort(arr);\n        \n        // Create a set to make the containment check faster.\n        Set<Integer> uniqueNumbers = new HashSet<>();\n        for (int num : arr) {\n            uniqueNumbers.add(num);\n        }\n\n        // Step 2: Initialize a map to store the number of binary trees that end with each element in the array.\n        Map<Integer, Integer> dp = new HashMap<>();\n        for (int num : arr) {\n            dp.put(num, 1);\n        }\n\n        // Step 3: Dynamic Programming\n        for (int i : arr) {\n            for (int j : arr) {\n                // If j is larger than the square root of i, break the loop because further j values won\'t be factors.\n                if (j > Math.sqrt(i)) break;\n                \n                // Check if j is a factor of i and i/j is in the set of unique numbers.\n                if (i % j == 0 && uniqueNumbers.contains(i / j)) {\n                    long product = (long) dp.get(j) * dp.get(i / j);\n                    \n                    // Update the number of binary trees ending with i based on the factors j and i/j.\n                    dp.put(i, (int) ((dp.get(i) + (i / j == j ? product : product * 2)) % MOD));\n                }\n            }\n        }\n\n        // Step 4: Calculate the final result.\n        int result = 0;\n        for (int value : dp.values()) {\n            result = (result + value) % MOD;\n        }\n        return result;\n    }\n}\n\n``` \n``` C++ []\n\nclass Solution {\nconst int MOD = 1e9 + 7;\npublic:\n    int numFactoredBinaryTrees(std::vector<int>& arr) {\n        // Step 1: Sort the input array.\n        std::sort(arr.begin(), arr.end());\n        \n        // Step 2: Create a set to store unique numbers in the array.\n        std::unordered_set<int> uniqueNumbers(arr.begin(), arr.end());\n        \n        // Step 3: Initialize a dynamic programming map.\n        std::unordered_map<int, int> dp;\n        for (int num : arr) {\n            dp[num] = 1;\n        }\n        \n        // Step 4: Dynamic Programming\n        for (int i : arr) {\n            for (int j : arr) {\n                // If j is larger than the square root of i, break the loop because further j values won\'t be factors.\n                if (j > std::sqrt(i)) break;\n                \n                // Check if j is a factor of i and if i/j is in the set of unique numbers.\n                if (i % j == 0 && uniqueNumbers.find(i / j) != uniqueNumbers.end()) {\n                    long long temp = static_cast<long long>(dp[j]) * dp[i / j];\n                    \n                    // Update the number of binary trees ending with i based on the factors j and i/j.\n                    if (i / j == j) {\n                        dp[i] = (dp[i] + temp) % MOD;\n                    } else {\n                        dp[i] = (dp[i] + temp * 2) % MOD;\n                    }\n                }\n            }\n        }\n        \n        // Step 5: Calculate the final result.\n        int result = 0;\n        for (auto& [_, val] : dp) {\n            result = (result + val) % MOD;\n        }\n        return result;\n    }\n};\n```\n``` Python []\n\nMOD = 10**9 + 7\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        # Step 1: Sort the input array.\n        arr.sort()\n        \n        # Step 2: Create a set to store unique numbers in the array.\n        unique_numbers = set(arr)\n        \n        # Step 3: Initialize a dynamic programming dictionary.\n        dp = {x: 1 for x in arr}\n        \n        # Step 4: Dynamic Programming\n        for i in arr:\n            for j in arr:\n                # If j is larger than the square root of i, break the loop because further j values won\'t be factors.\n                if j > i**0.5:\n                    break\n                \n                # Check if j is a factor of i and if i/j is in the set of unique numbers.\n                if i % j == 0 and i // j in unique_numbers:\n                    if i // j == j:\n                        # If j and i/j are the same, update dp[i] accordingly.\n                        dp[i] += dp[j] * dp[j]\n                    else:\n                        # If j and i/j are different, update dp[i] accordingly.\n                        dp[i] += dp[j] * dp[i // j] * 2\n                    dp[i] %= MOD\n        \n        # Step 5: Calculate the final result.\n        result = sum(dp.values()) % MOD\n        return result\n\n```\n``` JavaScript []\nconst MOD = 10**9 + 7;\nvar numFactoredBinaryTrees = function(arr) {\n\n    // Step 1: Sort the input array.\n    arr.sort((a, b) => a - b);\n    \n    // Step 2: Create a set to store unique numbers in the array.\n    const uniqueNumbers = new Set(arr);\n    \n    // Step 3: Initialize a dynamic programming object.\n    const dp = {};\n    for (let x of arr) {\n        dp[x] = 1;\n    }\n    \n    // Step 4: Dynamic Programming\n    for (let i of arr) {\n        for (let j of arr) {\n            // If j is larger than the square root of i, break the loop because further j values won\'t be factors.\n            if (j > Math.sqrt(i)) break;\n            \n            // Check if j is a factor of i and if i/j is in the set of unique numbers.\n            if (i % j === 0 && uniqueNumbers.has(i / j)) {\n                // Update the number of binary trees ending with i based on the factors j and i/j.\n                dp[i] += (i / j === j ? dp[j] * dp[j] : dp[j] * dp[i / j] * 2);\n                dp[i] %= MOD;\n            }\n        }\n    }\n    \n    // Step 5: Calculate the final result.\n    const result = Object.values(dp).reduce((acc, val) => (acc + val) % MOD, 0);\n    return result;\n}\n\n```\n``` C# []\npublic class Solution {\n    private const int MOD = 1000000007;\n\n    public int NumFactoredBinaryTrees(int[] arr) {\n        // Step 1: Sort the input array.\n        Array.Sort(arr);\n        \n        // Step 2: Create a HashSet to store unique numbers in the array.\n        HashSet<int> uniqueNumbers = new HashSet<int>(arr);\n        \n        // Step 3: Initialize a Dictionary for dynamic programming.\n        Dictionary<int, long> dp = new Dictionary<int, long>();\n        foreach (int num in arr) {\n            dp[num] = 1;\n        }\n        \n        // Step 4: Dynamic Programming\n        foreach (int i in arr) {\n            foreach (int j in arr) {\n                // If j is larger than the square root of i, break the loop because further j values won\'t be factors.\n                if (j > Math.Sqrt(i)) break;\n                \n                // Check if j is a factor of i and if i/j is in the set of unique numbers.\n                if (i % j == 0 && uniqueNumbers.Contains(i / j)) {\n                    long temp = dp[j] * dp[i / j];\n                    \n                    // Update the number of binary trees ending with i based on the factors j and i/j.\n                    dp[i] = (dp[i] + (i / j == j ? temp : temp * 2)) % MOD;\n                }\n            }\n        }\n        \n        // Step 5: Calculate the final result.\n        long result = 0;\n        foreach (long value in dp.Values) {\n            result = (result + value) % MOD;\n        }\n        return (int)result;\n    }\n}\n\n```\n``` PHP []\nclass Solution {\n    function numFactoredBinaryTrees($arr) {\n        // Step 1: Sort the input array in ascending order.\n        sort($arr);\n        \n        // Step 2: Create a hash map for faster containment checks.\n        $uniqueNumbers = array_flip($arr);\n        \n        // Step 3: Initialize a hash map for dynamic programming.\n        $dp = [];\n        foreach ($arr as $x) {\n            $dp[$x] = 1;\n        }\n\n        // Step 4: Dynamic Programming\n        foreach ($arr as $i) {\n            foreach ($arr as $j) {\n                // If $j is larger than the square root of $i, break the loop.\n                if ($j > sqrt($i)) break;\n\n                // Check if $j is a factor of $i and if $i/$j is in the unique numbers hash map.\n                if ($i % $j == 0 && isset($uniqueNumbers[$i / $j])) {\n                    // Calculate the temporary result.\n                    $temp = (int)((($dp[$j] * $dp[$i / $j]) % 1000000007) * ($i / $j == $j ? 1 : 2));\n                    \n                    // Update the number of binary trees ending with $i based on the factors $j and $i/$j.\n                    $dp[$i] = ($dp[$i] + $temp) % 1000000007;\n                }\n            }\n        }\n\n        // Step 5: Calculate the final result.\n        $result = 0;\n        foreach ($dp as $val) {\n            $result = ($result + $val) % 1000000007;\n        }\n        \n        return $result;\n    }\n}\n\n```\n![vote.jpg](https://assets.leetcode.com/users/images/da3ab02d-82e7-4276-9d7a-cdae1dd9c1eb_1698287692.8844771.jpeg)\n\n
['Dynamic Programming', 'Ordered Map', 'PHP', 'Ordered Set', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']