✅☑[C++/Java/Python/JavaScript] || 2 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n#### Approach 1(Maps)\n1. Initialize a modulo value mod to prevent integer 
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n#### ***Approach 1(Maps)***\n1. Initialize a modulo value `mod` to prevent integer overflow and create a map `mp` to store the count of factored binary trees for each number.\n1. `Sort` the input array in ascending order for efficient processing.\n1. Initialize the count for the first element in the array.\n1. Loop through the input array starting from the second element.\n1. For each element, iterate through the elements in the map and check if the current element is divisible by a map element and if the resulting factor is also present in the map.\n1. If the conditions are met, calculate the count for the current element by multiplying counts of factors and update the map.\n1. Calculate the total number of factored binary trees by summing up the counts in the map, using modulo to keep the result within bounds.\n1. Return the total number of factored binary trees.\n\n# Complexity\n- *Time complexity:*\n   $$O(n^2)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int mod = pow(10, 9) + 7; // Define a modulo value to prevent integer overflow.\n        map<int, long> mp; // Create a map to store the count of factored binary trees for each number.\n        sort(arr.begin(), arr.end()); // Sort the input array in ascending order.\n        mp[arr[0]] = 1; // Initialize the count for the first element in the array.\n\n        // Loop through the input array starting from the second element.\n        for (int i = 1; i < arr.size(); i++) {\n            long cnt = 1; // Initialize the count for the current element.\n\n            // Iterate through the elements in the map.\n            for (auto x : mp) {\n                int el = x.first; // Get an element from the map.\n\n                // Check if the current element in the array is divisible by the map element\n                // and if the resulting factor is also present in the map.\n                if (arr[i] % el == 0 && mp.find(arr[i] / el) != mp.end()) {\n                    // Calculate the count for the current element by multiplying counts of factors.\n                    cnt += mp[el] * mp[arr[i] / el];\n                }\n            }\n\n            mp[arr[i]] = cnt; // Store the computed count in the map for the current element.\n        }\n\n        int ans = 0; // Initialize the answer variable.\n\n        // Calculate the total number of factored binary trees by summing up the counts in the map.\n        for (auto a : mp) {\n            ans = (ans + a.second) % mod; // Use modulo to keep the result within bounds.\n        }\n\n        return ans; // Return the total number of factored binary trees.\n    }\n};\n\n\n```\n\n```C []\n#include <stdio.h>\n#include <stdlib.h>\n#include <math.h>\n\n// Define a structure to represent key-value pairs in the map\ntypedef struct {\n    int key;\n    long value;\n} KeyValuePair;\n\n// Function to compare two key-value pairs for sorting\nint compare(const void* a, const void* b) {\n    return ((KeyValuePair*)a)->key - ((KeyValuePair*)b)->key;\n}\n\nint numFactoredBinaryTrees(int* arr, int arrSize) {\n    long mod = (long)pow(10, 9) + 7; // Define a modulo value to prevent integer overflow.\n    \n    // Create an array of key-value pairs to store the count of factored binary trees for each number.\n    KeyValuePair* mp = (KeyValuePair*)malloc(arrSize * sizeof(KeyValuePair));\n    \n    // Sort the input array in ascending order.\n    qsort(arr, arrSize, sizeof(int), compare);\n    \n    // Initialize the count for the first element in the array.\n    mp[0].key = arr[0];\n    mp[0].value = 1;\n    \n    // Loop through the input array starting from the second element.\n    for (int i = 1; i < arrSize; i++) {\n        long cnt = 1; // Initialize the count for the current element.\n        \n        // Iterate through the elements in the map.\n        for (int j = 0; j < i; j++) {\n            int el = mp[j].key; // Get an element from the map.\n            \n            // Check if the current element in the array is divisible by the map element\n            // and if the resulting factor is also present in the map.\n            if (arr[i] % el == 0) {\n                int factor = arr[i] / el;\n                for (int k = 0; k < i; k++) {\n                    if (mp[k].key == factor) {\n                        // Calculate the count for the current element by multiplying counts of factors.\n                        cnt += mp[j].value * mp[k].value;\n                        break;\n                    }\n                }\n            }\n        }\n        \n        mp[i].key = arr[i];\n        mp[i].value = cnt; // Store the computed count in the map for the current element.\n    }\n    \n    long ans = 0; // Initialize the answer variable.\n    \n    // Calculate the total number of factored binary trees by summing up the counts in the map.\n    for (int i = 0; i < arrSize; i++) {\n        ans = (ans + mp[i].value) % mod; // Use modulo to keep the result within bounds.\n    }\n    \n    free(mp); // Free the dynamically allocated memory.\n    \n    return (int)ans; // Return the total number of factored binary trees.\n}\n\nint main() {\n    int arr[] = {2, 4, 5};\n    int arrSize = sizeof(arr) / sizeof(arr[0]);\n    int result = numFactoredBinaryTrees(arr, arrSize);\n    printf("Total number of factored binary trees: %d\\n", result);\n    return 0;\n}\n\n\n\n```\n\n```Java []\nimport java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\n        int mod = (int) Math.pow(10, 9) + 7; // Define a modulo value to prevent integer overflow.\n        Arrays.sort(arr); // Sort the input array in ascending order.\n        Map<Integer, Long> mp = new HashMap<>(); // Create a map to store the count of factored binary trees for each number.\n        mp.put(arr[0], 1L); // Initialize the count for the first element in the array.\n\n        // Loop through the input array starting from the second element.\n        for (int i = 1; i < arr.length; i++) {\n            long cnt = 1; // Initialize the count for the current element.\n\n            // Iterate through the elements in the map.\n            for (Map.Entry<Integer, Long> entry : mp.entrySet()) {\n                int el = entry.getKey(); // Get an element from the map.\n\n                // Check if the current element in the array is divisible by the map element\n                // and if the resulting factor is also present in the map.\n                if (arr[i] % el == 0 && mp.containsKey(arr[i] / el)) {\n                    // Calculate the count for the current element by multiplying counts of factors.\n                    cnt += entry.getValue() * mp.get(arr[i] / el);\n                }\n            }\n\n            mp.put(arr[i], cnt); // Store the computed count in the map for the current element.\n        }\n\n        long ans = 0; // Initialize the answer variable.\n\n        // Calculate the total number of factored binary trees by summing up the counts in the map.\n        for (long value : mp.values()) {\n            ans = (ans + value) % mod; // Use modulo to keep the result within bounds.\n        }\n\n        return (int) ans; // Return the total number of factored binary trees.\n    }\n}\n\n\n```\n\n```python3 []\nclass Solution:\n    def numFactoredBinaryTrees(self, arr):\n        mod = 10**9 + 7  # Define a modulo value to prevent integer overflow.\n        arr.sort()  # Sort the input list in ascending order.\n        mp = {}  # Create a dictionary to store the count of factored binary trees for each number.\n        mp[arr[0]] = 1  # Initialize the count for the first element in the list.\n\n        # Loop through the input list starting from the second element.\n        for i in range(1, len(arr)):\n            cnt = 1  # Initialize the count for the current element.\n\n            # Iterate through the elements in the dictionary.\n            for el in mp:\n                # Check if the current element in the list is divisible by the dictionary element\n                # and if the resulting factor is also present in the dictionary.\n                if arr[i] % el == 0 and arr[i] // el in mp:\n                    # Calculate the count for the current element by multiplying counts of factors.\n                    cnt += mp[el] * mp[arr[i] // el]\n\n            mp[arr[i]] = cnt  # Store the computed count in the dictionary for the current element.\n\n        ans = 0  # Initialize the answer variable.\n\n        # Calculate the total number of factored binary trees by summing up the counts in the dictionary.\n        for a in mp:\n            ans = (ans + mp[a]) % mod  # Use modulo to keep the result within bounds.\n\n        return ans  # Return the total number of factored binary trees.\n\n\n```\n\n```javascript []\nvar numFactoredBinaryTrees = function(arr) {\n    const mod = 10**9 + 7; // Define a modulo value to prevent integer overflow.\n    arr.sort((a, b) => a - b); // Sort the input array in ascending order.\n    const mp = new Map(); // Create a Map to store the count of factored binary trees for each number.\n    mp.set(arr[0], 1); // Initialize the count for the first element in the array.\n\n    // Loop through the input array starting from the second element.\n    for (let i = 1; i < arr.length; i++) {\n        let cnt = 1; // Initialize the count for the current element.\n\n        // Iterate through the elements in the Map.\n        for (const [el, value] of mp) {\n            // Check if the current element in the array is divisible by the Map element\n            // and if the resulting factor is also present in the Map.\n            if (arr[i] % el === 0 && mp.has(arr[i] / el)) {\n                // Calculate the count for the current element by multiplying counts of factors.\n                cnt += value * mp.get(arr[i] / el);\n            }\n        }\n\n        mp.set(arr[i], cnt); // Store the computed count in the Map for the current element.\n    }\n\n    let ans = 0; // Initialize the answer variable.\n\n    // Calculate the total number of factored binary trees by summing up the counts in the Map.\n    for (const value of mp.values()) {\n        ans = (ans + value) % mod; // Use modulo to keep the result within bounds.\n    }\n\n    return ans; // Return the total number of factored binary trees.\n};\n\n```\n\n\n---\n#### ***Approach 2(DP)***\n1. The code uses dynamic programming to calculate the number of factored binary trees for each number in the input array.\n1. It sorts the input array for easier iteration and creates a set for efficient lookups.\n1. The `dp` map stores the count of factored binary trees for each number, initializing each count to 1.\n1. It iterates through each element in the array and checks for factors within the array. If factors are found, it calculates the count of binary trees by multiplying the counts of the factors.\n1. The modulo operation is used to keep the result within bounds to prevent integer overflow.\n1. Finally, it sums up all the counts in the map to obtain the total number of factored binary trees.\n\n# Complexity\n- *Time complexity:*\n   $$O(n^2)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\nconst int MOD = 1e9 + 7;\n\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(std::vector<int>& arr) {\n        std::sort(arr.begin(), arr.end()); // Sort the input array in ascending order.\n        std::unordered_set<int> s(arr.begin(), arr.end()); // Create a set for faster element lookup.\n        std::unordered_map<int, int> dp; // Create a map to store the count of factored binary trees for each number.\n        \n        for (int x : arr)\n            dp[x] = 1; // Initialize the count for each element to 1, representing the tree with just the element itself.\n        \n        for (int i : arr) {\n            for (int j : arr) {\n                if (j > std::sqrt(i))\n                    break; // If j is greater than the square root of i, we can break because further factors won\'t be found.\n                \n                if (i % j == 0 && s.find(i / j) != s.end()) {\n                    long long temp = (long long)dp[j] * dp[i / j]; // Calculate the count by multiplying counts of factors.\n                    \n                    if (i / j == j) {\n                        dp[i] = (dp[i] + temp) % MOD; // If the factor is the same, we add the count once.\n                    } else {\n                        dp[i] = (dp[i] + temp * 2) % MOD; // If the factors are different, we add the count twice.\n                    }\n                }\n            }\n        }\n        \n        int result = 0;\n        for (auto& [_, val] : dp) {\n            result = (result + val) % MOD; // Sum up all the counts in the map.\n        }\n        return result; // Return the total number of factored binary trees.\n    }\n};\n\n\n```\n\n```C []\n#define MOD 1000000007\n\nint numFactoredBinaryTrees(int* arr, int arrSize) {\n    qsort(arr, arrSize, sizeof(int), compare);\n    int s[arrSize];\n    for (int i = 0; i < arrSize; i++) {\n        s[i] = arr[i];\n    }\n    int dp[arrSize];\n    for (int i = 0; i < arrSize; i++) {\n        dp[i] = 1;\n    }\n\n    for (int i = 0; i < arrSize; i++) {\n        for (int j = 0; j < arrSize; j++) {\n            if (s[j] > sqrt(arr[i])) {\n                break;\n            }\n            if (arr[i] % s[j] == 0) {\n                long long temp = (long long)dp[j] * dp[binarySearch(s, arrSize, arr[i] / s[j])];\n                if (arr[i] / s[j] == s[j]) {\n                    dp[i] = (dp[i] + temp) % MOD;\n                } else {\n                    dp[i] = (dp[i] + temp * 2) % MOD;\n                }\n            }\n        }\n    }\n\n    int result = 0;\n    for (int i = 0; i < arrSize; i++) {\n        result = (result + dp[i]) % MOD;\n    }\n    return result;\n}\n\n\n\n```\n\n```Java []\nimport java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass Solution {\n    public int numFactoredBinaryTrees(int[] arr) {\n        int MOD = 1000000007;\n        Arrays.sort(arr);\n        Map<Integer, Integer> dp = new HashMap<>();\n        int[] s = Arrays.copyOf(arr, arr.length);\n\n        for (int x : arr) {\n            dp.put(x, 1);\n        }\n\n        for (int i : arr) {\n            for (int j : arr) {\n                if (j > Math.sqrt(i)) {\n                    break;\n                }\n                if (i % j == 0 && Arrays.binarySearch(s, i / j) >= 0) {\n                    long temp = (long) dp.get(j) * dp.get(i / j);\n                    if (i / j == j) {\n                        dp.put(i, (int) ((dp.get(i) + temp) % MOD));\n                    } else {\n                        dp.put(i, (int) ((dp.get(i) + temp * 2) % MOD));\n                    }\n                }\n            }\n        }\n\n        int result = 0;\n        for (int val : dp.values()) {\n            result = (result + val) % MOD;\n        }\n        return result;\n    }\n}\n\n\n```\n\n```python3 []\nclass Solution:\n    def numFactoredBinaryTrees(self, arr: List[int]) -> int:\n        MOD = 1000000007\n        arr.sort()\n        dp = {}\n        s = arr.copy()\n\n        for x in arr:\n            dp[x] = 1\n\n        for i in arr:\n            for j in arr:\n                if j > int(i ** 0.5):\n                    break\n                if i % j == 0 and i // j in s:\n                    temp = dp[j] * dp[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        result = 0\n        for val in dp.values():\n            result = (result + val) % MOD\n        return result\n\n\n```\n\n```javascript []\n/**\n * @param {number[]} arr\n * @return {number}\n */\nvar numFactoredBinaryTrees = function(arr) {\n    const MOD = 1000000007;\n    arr.sort((a, b) => a - b);\n    const dp = new Map();\n    const s = [...arr];\n\n    for (const x of arr) {\n        dp.set(x, 1);\n    }\n\n    for (const i of arr) {\n        for (const j of arr) {\n            if (j > Math.sqrt(i)) {\n                break;\n            }\n            if (i % j === 0 && s.includes(i / j)) {\n                const temp = BigInt(dp.get(j)) * BigInt(dp.get(i / j));\n                if (i / j === j) {\n                    dp.set(i, (Number(dp.get(i)) + Number(temp)) % MOD);\n                } else {\n                    dp.set(i, (Number(dp.get(i)) + Number(temp * 2n)) % MOD);\n                }\n            }\n        }\n    }\n\n    let result = 0;\n    for (const val of dp.values()) {\n        result = (result + val) % MOD;\n    }\n    return result;\n};\n\n```\n\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Hash Table', 'Dynamic Programming', 'C', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']