C++, Dynamic Programming, Two Pointer
This solution revolves around constructing solutions for larger numbers provided in arr by first building solutions for smaller numbers in arr and then building
This solution revolves around constructing solutions for larger numbers provided in `arr` by first building solutions for smaller numbers in `arr` and then building these solutions using dynamic programming.\n\nWe start by sorting `arr` so that we can traverse it in an increasing order, since larger numbers cannot be factors of smaller numbers that precede them, but smaller numbers in  `arr` can be factors of larger numbers in `arr`.\n\nThen, we build our `dp` array of type `long` and initialize all elements to 1. This is because every element in the `dp` represents something that appears in `arr`, and so by definition, there is *at least* one way to build said element as a binary tree (i.e. an empty tree rooted at that element). We use type `long` to avoid overflow error in our calculations.\n\nFrom here, we use `dppos` to represent the element in `arr` currently under consideration. For this element, we are aiming to answer the question ***for this element, using smaller elements in the array, how many ways can we represent this element as a binary tree under the rules stipulated in the problem description?*** To do so, we iterate through all elements in `arr` smaller than the given element using two pointers, with a left pointer starting at the smallest element and a right pointer starting at the highest element. At each point, we run into three cases:\n1. If the product of `arr[left]` and `arr[right]` exceed the given element, we know our product is too large, so we decrement `right`.\n2. If the product of `arr[left]` and `arr[right]` is less than the given element, we know our product is too small, so we increment `left`.\n3. Otherwise, we have found a way to represent the given element as a factor of two smaller elements, so we increase our count of the number of ways to make the current element (i.e. `dp[dppos]`) by the product of the number of ways to make each of the smaller elements, because for each subtree rooted at the given element, we have a choice on which "way" we are going to make the factor of the larger element. Note that if we are multiplying the same element twice, we do not multiply the overall product by 2, since the same element is being used twice, creating an inherent symmetry in the tree.\n\nTo avoid overflow, we cast operand to type `long` and use the modulo operator at the end of each iteration. Using a global `total` variable allows us to keep track of the total number of trees capable of being made with this array as we go along, which we return as our final answer.\n\nThis method requires linear extra space in the number of elements in `arr` and requires quadratic time, since for each element in `arr` we are looping through elements smaller than it.\n\n```\nint numFactoredBinaryTrees(vector<int>& arr) {\n\tsort(arr.begin(), arr.end());\n\tvector<long> dp(arr.size(), 1);\n\tint total = 0;\n\tfor (int dppos = 0; dppos < dp.size(); dppos++) {\n\t\tint left = 0, right = dppos - 1;\n\t\twhile (left <= right) {\n\t\t\tif (long(arr[left]) * arr[right] > arr[dppos]) {\n\t\t\t\tright--;\n\t\t\t} else if (long(arr[left]) * arr[right] < arr[dppos]) {\n\t\t\t\tleft++;\n\t\t\t} else {\n\t\t\t\tif (left == right) {\n\t\t\t\t\tdp[dppos] += (dp[left] * dp[right]);\n\t\t\t\t} else {\n\t\t\t\t\tdp[dppos] += 2 * (dp[left] * dp[right]);\n\t\t\t\t}\n\t\t\t\tleft++;\n\t\t\t\tright--;\n\t\t\t}\n\t\t}\n\t\ttotal = ((total % 1000000007) + dp[dppos]) % 1000000007;   \n\t}\n\treturn total;\n}\n```
[]