C++ | 2 Approach | 2 pointer, linear, and Map find | Dynamic Programming | Maths
\n\nLet\'s understand 2 basic things \n\n1. For any node, it can be root with total nodes in tree as 1 \n2. If a root is having child1 and child2 as their left 
\n\nLet\'s understand 2 basic things \n\n1. For any node, it can be root with total nodes in tree as 1 \n2. If a root is having child1 and child2 as their left and right chidren then answer for that node as root of tree is 1 + (child1 as root * child2 as root)\n\n\nThe basic idea is to store the no of trees that can be formed having node as the root, then we can solve the problem very easily\nSo for any node we will find the children and update the answer as (ans(child1) * ans(child2) + 1)\n\nWe are adding 1 because each node can form a tree having itself as root and having no children\n\n**Okay so how to search the factors?**\n\n1. One way can be like we can create all factor pairs for the number and search it inside the map, but can you guess, how time consuming this process can be\n2. The other way is that we can sort the array the if index i is that number, then we can clearly say that its factors lies from 0 to i-1 because any number in array greater than ith index will be greater than the number so we don\'t need to look after that\n\n\n**Now again how can we find the factors in 0 to i-1?**\nAgain there are 2 ways\n1. we iterate j  from  0 to i-1 and check wheather number is divided by arr[j], if it is divided then it is one of the factors then the other factor will be number / arr[j], as arr[j]*other factor = number, we find that the other factor is present in map or not\n2. The other way is that we can have a 2-pointer search from 0 to i-1 \n\t\tleft = 0 and right = i-1\n\t\twe do a 2-pointer search and find that when arr[left]*arr[right] == number, then arr[left] and arr[right] are the factors \n\t\there is also a crunch, in step 1 let us suppose [2, 5, 10 ], we will calculare answer for 2 and 5 saperately\n\t\tbut in this case if we have child1 and child2 then we will directly multiply answer by 2 because [root, child1, child2] and [root, child2, child1] have same answer\n\n\n\nAlgorithm -\n1. create an unordered map mp to store the answer for each particular node\n2. sort the array for factors search\n3. iterate the array and mp[arr[i]] = 1\n\tsearch the factor, if factor is fiund then update mp[arr[i]] = product of the answers of both the children for linear search and when doing 2-pointer search update the answer as mp[arr[i]] = product of answers of chilren * 2\n\n4. add mp[arr[i]] to answer \n5. return answer\n\n\n\n\n\n\n\nLinear search Code\n\n\n\n```\nclass Solution {\n   \npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int mod = 1000000007;\n        int n = arr.size();\n        unordered_map<long long,long long> mp;\n        sort(arr.begin(), arr.end());\n        \n        \n        int ans = 0;\n        \n        for(int i = 0 ; i < n ; i++){\n            mp[arr[i]] += 1;\n            for(int j = 0 ; j < i ; j++){\n                if(arr[i] % arr[j] == 0){\n                    int child1 = arr[j];\n                    int child2 = arr[i]/arr[j];\n                    if(mp.find(child2) != mp.end()){\n                        mp[arr[i]] += (mp[child1] * mp[child2])%mod;\n                        mp[arr[i]] %= mod;\n                    }\n                }\n            }\n            ans += mp[arr[i]];\n            ans %= mod;\n        }\n        \n        return ans;\n \n    }\n};\n```\n\n\n2-pointer Search Code\n\n```\nclass Solution {\n   \npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int mod = 1000000007;\n        int n = arr.size();\n        unordered_map<long long,long long> mp;\n        sort(arr.begin(), arr.end());\n        \n        \n        int ans = 0;\n        \n        for(int i = 0 ; i < n ; i++){\n            mp[arr[i]] += 1;\n            int left = 0;\n            int right = i-1;\n            \n            while(left <= right){\n                long long child1 = arr[left];\n                long long child2 = arr[right];\n                long long product = (child1 * child2);\n                if(product == arr[i]){\n                   if(left == right){\n\t\t\t\t\t   mp[arr[i]] += (mp[arr[left]] * mp[arr[right]] )%mod;   \n                   }\n                  else{\n                       mp[arr[i]] += (mp[arr[left]] * mp[arr[right]] * 2)%mod;\n                        \n                    }\n                  mp[arr[i]] %= mod;\n                  left += 1;\n                  right -= 1;\n                }\n                \n             if(product < arr[i]){\n                    left += 1;\n             }\n             else if(product > arr[i]){\n                    right -= 1;\n             }\n           }\n            \n            \n            ans += mp[arr[i]];\n            ans %= mod;\n        }\n        \n        return ans;\n \n    }\n};\n```\nBoth the approaches have same time complexity\n\nTime Complexity - O(N*N) \nSpace Complexity - O(N)
['Two Pointers', 'Dynamic Programming', 'C', 'Sorting', 'C++']